冒泡排序的實現及優化和變形

2019 年 10 月 12 日
筆記

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 }