[演算法] 氣泡排序法 Bubble Sort

　　氣泡排序法是經典的三大 O(n^2) 排序演算法之一，同時他也是三者中最簡單的，大陸翻作「冒泡排序法」，因為他的概念是最大或最小的物件會慢慢地浮到飄到該去的位置。

　　氣泡排序法的在不做任何最佳化的狀況下，因為無法判斷數列是否已經排好了，也會傻傻的作O(n^2)次的交換和比較來確保數列排序完成，故最佳狀況也需要 O(n^2)。因此，大多數的氣泡排序都會加上一個旗標(flag)用來判段當一輪的交換完成時是否有任何物件被交換，如果沒有其實就是完成了，可以將最佳狀況變為 O(n)。

　　特別要注意的是，氣泡排序法所需要的最壞狀況交換操作次數遠超過選擇排序法跟插入排序法，雖然他們都是 O(n^2)，但那是指比較操作加上交換操作的結果。氣泡排序法最糟狀況需要做  n*(n-1)/2 次交換，選擇排序法只要 n - 1 次，插入排序法要(((n-1)^2)/2)/3 次，都會比氣泡排序法德有效率。因此，氣泡排序法只適用在非常少量的數據，一般不太會用到 (但他就是簡單)。

複雜度：

• 時間：最佳 O(n)  [使用 flag] 最差 O(n^2)
• 空間：O(n), O(1) 輔助用

步驟：

1. 將序列式為兩段，已排序和未排序，一開始整個序列都屬於未排序。
2. 從未排序頭比較相鄰兩物件，若前者較大(小)就交換他們。
3. 不斷向後比較、交換直到未排序序列的最後一個物件。此時未排序序列中最大或最小的物件會被成為已排序序列的頭。
4. 重複 n*(n -1)/2 次，直到所有物件都進入已排序序列。

Java 簡單實現：

public class BubbleSort {
     public void sort(int[] array) {
          // 未排序序列的尾
          for(int i = array.length - 1; i > 0; --i) {
               // 交換整個未排列序列
               for(int j = 0; j < i ; ++j) {
                    if(array[j] > array[j+1]) {
                         int tmp = array[j];
                         array[j] = array[j + 1];
                         array[j + 1] = tmp;
                    }
               }
          }
     }
}

Flag 最佳化版本：

public class BubbleSort {
     public void sort(int[] array) {
          // 未排序序列的尾
          for(int i = array.length - 1; i > 0; --i) {
               boolean isChange = false;
               // 交換整個未排列序列
               for(int j = 0; j < i ; ++j) {
                    if(array[j] > array[j+1]) {
                         int tmp = array[j];
                         array[j] = array[j + 1];
                         array[j + 1] = tmp;
                         isChange = true;
                    }
               }
               // 都沒有交換到東西就排序完成
               if( ! isChange) {
                   break;
               }
          }
     }
}

範例影片：

參考資料：

1. Wiki 冒泡排序