Bubble Sort 氣泡排序法

wiki有此演算法的詳細介紹: Wiki Bubble Sort

我們想要以遞增順序來sort一個 [A1..An] 的array，
首先比較A1和A2，若 A1 > A2，則 swap(A1,A2)，
一直重複進行此動作到An-1和An，就可以保證An是array中最大的元素。

接下來，我們重複以上的動作，
比較 [A1..An-1]，使得An-1成為subarray中的最大元素。
不斷重複此動作，比較 [A1..An-2]、[A1..An-3]...，
我們可以確定最右邊的元素為每個subarray中的最大的元素，
最後比較完 [A1..A2] 時，就可以將array以遞增的順序排序好了。

以下為用java實現此演算法。

class BubbleSort {
    static final boolean INC_ORDER = true;
    static final boolean DEC_ORDER = false;

    static void sort(int[] array, boolean order) {
        int temp;
        if (order==INC_ORDER) {
            for (int i=array.length-1; i>0; --i) {
                for (int j=0; j<i; ++j) {
                    if (array[j] > array[j+1]) {
                        temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                }
            }
        } else {
            for (int i=0; i<array.length; ++i) {
                for (int j=array.length-1; j>i; --j) {
                    if (array[j] > array[j-1]) {
                        temp = array[j];
                        array[j] = array[j-1];
                        array[j-1] = temp;
                    }
                }
            }            
        }
    }
}

我們實作了遞增與遞減兩種排法，
其中遞增是從左邊排到右邊，而遞減是從右邊排到左邊。
然而，不管從哪邊排到哪邊都是沒差的，
重點在 if 條件式，
要遞增排序時，把比較大的元素換到右邊；
要遞減排序時，把比較大的元素換到左邊。
所以Bubble Sort有很多種寫法。

Bubble Sort的時間複雜度為 O(n²)，
無論是best-case或是worst-case，都要跑那雙層迴圈。
因此，此排序法的實用性是相當低的，
基本上不會拿這個排序法來做排序。
這個排序法只是讓初學sorting algorithm的人有最基本的觀念。