Java實作冒泡排序演算法及對其的簡單最佳化範例

原理

冒泡排序大概是所有程式設計師都會用的演算法，也是最熟悉的演算法之一。
它的思路並不複雜：
設現在要給數組arr[]排序，它有n個元素。
1.如果n=1：顯然不用排了。 （實際上這個討論似乎沒什麼必要）
2.如果n>1：
（1）我們從第一個元素開始，把每兩個相鄰元素進行比較，如果前面的元素比後面的大，那麼在最後的結果裡面前者肯定排在後面。所以，我們把這兩個元素交換。然後進行下兩個相鄰的元素的比較。如此直到最後一對元素比較完畢，則第一輪排序完成。可以肯定，最後一個元素一定是數組中​​最大的（因為每次都把相對大的放到後面了）。
（2）重複上述過程，這次我們無需考慮最後一個，因為它已經排好了。
（3）如此直到只剩下一個元素，這個元素一定是最小的，那麼我們的排序可以結束了。顯然，進行了n-1次排序。
上述過程中，每次（或稱為「輪」）排序都會有一個數字從某個位置慢慢「浮動」到最終的位置（畫個示意圖，把數組畫成垂直的就可以看出來），就像冒泡一樣，所以，它被稱為“冒泡排序法”。

程式碼實作：

public class BubbleSort{
   public static void main(String[] args){
     int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
     for (int i = 0; i < score.length -1; i++){  //最多做n-1趟排序
       for(int j = 0 ;j < score.length - i - 1; j++){  //对当前无序区间score[0......length-i-1]进行排序(j的范围很关键，这个范围实在逐步缩小的)
         if(score[j] < score[j + 1]){  //把小的值交换到后面
           int temp = score[j];
           score[j] = score[j + 1];
           score[j + 1] = temp;
         }
       }      
       System.out.print("第" + (i + 1) + "次排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
       }
       System.out.println("");
     }
       System.out.print("最终排序结果：");
       for(int a = 0; a < score.length; a++){
         System.out.print(score[a] + "\t");
     }
   }
 }

演算法效能/複雜度
我們忽略掉循環變數自增和初始化的時間。先分析演算法的比較次數。很容易看出，上面這種未經任何改進的冒泡排序無論輸入資料如何都會進行n-1輪排序，而每輪排序需要比較的次數從n-1遞減到0。那麼，總的比較次數即是 (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2。 （由於我不知道這裡如何打出平方，這裡，我用n^2代表平方，下同）
再來看下賦值次數。這裡的賦值是指其中的交換操作，對於上述程式碼，1次交換等於三次賦值。由於並非每次都必須交換，因此，賦值操作的次數與輸入資料有關。最佳情況(best case)下，即一開始就是有序的情況下，賦值次數為0。 而最壞情況(worst case)下，賦值次數為(n-1)n/2。假設輸入資料平均（或說「完全隨機」）分佈，那麼大約有交換次數為比較次數的一半。由上面的結果，可以得到平均情況(average case)下，賦值次數為3/2 * (n^2)/2 = 3/4*(n^2).
綜上，無論在何種情況下，冒泡排序空間複雜度（額外空間）總是O(1)。

改進
在資料完全有序的時候展現出最適時間複雜度，為O(n)。其他情況下，幾乎總是O(n^2)。因此，演算法在資料基本上有序的情況下，效能最好。
但是，上面的程式碼怎麼可能出現O(n)複雜度呢？實際上，因為上面注重的是基本思路，因此只是最簡單情況，要使演算法在最佳情況下有O(n)複雜度，需要做一些改進，改進後的程式碼為：

public static void bubbleSort(int[] arr) {
  int temp = 0;
  boolean swap;
  for (int i = arr.length - 1; i > 0; --i) { // 每次需要排序的长度
    swap=false;
    for (int j = 0; j < i; ++j) { // 从第一个元素到第i个元素
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap=true;
      }
    }//loop j
    if (swap==false){
      break;
    }
  }//loop i
}// method bubbleSort

實際上，由於在大量資料的情況下幾乎不使用冒泡排序，而使用小資料的時候增加的布林變數反而會造成額外的開銷。所以個人認為上面改進後的演算法只是純理論的，通常，冒泡排序就寫前面一種就行了。

演算法穩定性
容易看出，在相鄰元素相等時，我們並不需要交換它們的位置，所以，冒泡排序是穩定排序。

演算法適用場景
冒泡排序思路簡單，程式碼也簡單，特別適合小數據的排序。但是，由於演算法複雜度較高，在資料量大的時候不適合使用。如果一定要在較多資料的時候使用，最好先對演算法加以改進，例如選擇排序法。

更多Java實現冒泡排序演算法及對其的簡單優化範例相關文章請關注PHP中文網！