1.概述
冒泡排序是一種簡單的排序演算法，它重復地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來，走訪數列的作業是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成，這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端，在一般面試中也是最容易碰到的排序演算法，
演算法描述
- 比較相鄰的元素，如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的作業，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；
- 針對所有的元素重復以上的步驟，除了最后一個；
- 重復步驟1~3，直到排序完成，
2.基本實作
參考代碼如下
pojo類
1 public class pojo { 2 public int[] s; 3 public pojo(){} 4 //產生n個隨機整數 5 public pojo(int n){ 6 s=new int[n]; 7 for(int i=0;i<n;i++) 8 s[i]=new Random().nextInt(n); 9 } 10 //產生n個有序整數,falg為true為順序,false為逆序 11 public pojo(int n,boolean falg){ 12 s=new int[n]; 13 if(falg){ 14 for(int i=0;i<n;i++) 15 s[i]=i; 16 }else{ 17 for(int i=0;i<n;i++) 18 s[i]=n-i; 19 } 20 } 21 //回傳前n個數總和 22 public long average(int n){ 23 long sum=0; 24 for(int i=0;i<n;i++) 25 sum+=s[i]; 26 return sum; 27 } 28 }
maopao類
1 public class maopao { 2 public static void sort(int[] s){ 3 for(int i=0;i<s.length;i++){ 4 for(int j=0;j<s.length-1-i;j++){ 5 if(s[j]>s[j+1]){ 6 s[j]=s[j]+s[j+1]; 7 s[j+1]=s[j]-s[j+1]; 8 s[j]=s[j]-s[j+1]; 9 } 10 } 11 } 12 } 13 public static void main(String[] args) { 14 pojo a=new pojo(10000); 15 int []s=a.s; 16 System.out.println(Arrays.toString(s)); 17 long startTime=System.nanoTime(); //獲取開始時間 18 sort(s); 19 long endTime=System.nanoTime(); //獲取結束時間 20 System.out.println(Arrays.toString(s)); 21 System.out.println("冒泡排序程式運行時間："+(endTime-startTime)+"ns"+"\t"+"陣列長度為:"+s.length); 22 } 23 }
運行結果
注意代碼中"s[j]=s[j]+s[j+1];s[j+1]=s[j]-s[j+1];s[j]=s[j]-s[j+1];",這段代碼意思為s[j]與s[j+1]的值交換
3.優化
思考一下，當需要排序的資料是排好的或者接近排好的，這樣的話在回圈結束前就已經排好了，但是排序還是會回圈判斷下去，這樣會多做不少無用功，那有什么辦法讓回圈停止呢？
我們發現在一次冒泡回圈中，如果當前元素與下一個元素不用交換、下一個元素與下下個元素不用交換、下下個元素...那么當前元素一直到最后一個元素一定是排好的，而回圈遍歷到當前元素時，第一個元素到當前元素已經是排好的了，所有整體就第一個元素到最后一個元素都排好了，可以直接結束了，
參考代碼如下
1 public class maopao1 { 2 public static void sort(int[] s){ 3 for(int i=0;i<s.length;i++){ 4 boolean flag=false; 5 for(int j=0;j<s.length-1-i;j++){ 6 if(s[j]>s[j+1]){ 7 s[j]=s[j]+s[j+1]; 8 s[j+1]=s[j]-s[j+1]; 9 s[j]=s[j]-s[j+1]; 10 flag=true; 11 } 12 } 13 if(!flag) 14 break; 15 } 16 } 17 public static void main(String[] args) { 18 pojo a=new pojo(10000); 19 int []s=a.s; 20 System.out.println(Arrays.toString(s)); 21 long startTime=System.nanoTime(); //獲取開始時間 22 sort(s); 23 long endTime=System.nanoTime(); //獲取結束時間 24 System.out.println(Arrays.toString(s)); 25 System.out.println("優化冒泡排序程式運行時間："+(endTime-startTime)+"ns"+"\t"+"陣列長度為:"+s.length); 26 } 27 }
運行結果
我在這里增加了一個flag變數來做標記，當滿足條件后直接跳出回圈，
發現沒有，運行時間上基本沒什么變化，但是注意我上面說了，當需要排序的資料是排好的或者接近排好的，優化效果就非常明顯了，
改變上面maopao1類的代碼
這個表示獲取從小到大的1-10000排列的陣列，我們的目標也是從小打大排序，
結果如下
3.變形
我在這里講一種新的排序，它叫雞尾酒排序，或者叫快樂小時排序，當然它不止這兩種叫法，他是冒泡排序的一種變形，是基于冒泡排序的，
他的原理是：先找到最小的數字，把他放到第一位，然后找到最大的數字放到最后一位，然后再找到第二小的數字放到第二位，再找到第二大的數字放到倒數第二位，以此類推，直到完成排序，也就是雙向的冒泡，
參考代碼如下
1 public class maopao2 { 2 public static void sort(int[] s){ 3 int left=0,right=s.length-1; 4 while(left<right){ 5 //同優化冒泡排序 6 boolean flag=false; 7 //從右向左冒泡，找最小的 8 for(int i=right;i>left;i--) 9 if(s[i]<s[i-1]){ 10 s[i]=s[i]+s[i-1]; 11 s[i-1]=s[i]-s[i-1]; 12 s[i]=s[i]-s[i-1]; 13 flag=true; 14 } 15 left++; 16 //從左向右冒泡，找最大的 17 for(int i=left;i<right;i++) 18 if(s[i]>s[i+1]){ 19 s[i]=s[i]+s[i+1]; 20 s[i+1]=s[i]-s[i+1]; 21 s[i]=s[i]-s[i+1]; 22 flag=true; 23 } 24 right--; 25 if(!flag) 26 break; 27 } 28 } 29 public static void main(String[] args) { 30 pojo a=new pojo(10000); 31 int []s=a.s; 32 System.out.println(Arrays.toString(s)); 33 long startTime=System.nanoTime(); //獲取開始時間 34 sort(s); 35 long endTime=System.nanoTime(); //獲取結束時間 36 System.out.println(Arrays.toString(s)); 37 System.out.println("雞尾酒排序程式運行時間："+(endTime-startTime)+"ns"+"\t"+"陣列長度為:"+s.length); 38 } 39 }
運行結果
雖然運行時間沒有多大改變，但是在某些特定的環境下是要優于冒泡排序的，
改變maopao2類代碼：
運行結果：
改變maopao2類代碼：
運行結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139961.html
標籤：其他
上一篇：telnet百度不通，telnet自己也不通，是因為對方沒開telnet嗎
下一篇：二分查找