【演算法】氣泡排序法 (Bubble Sort)

氣泡排序法本質上也是一種選擇排序法, 它使用 "氣泡" 策略, 讓最大的元素像氣泡一樣冒到最上面, 也就是與陣列最後一個元素進行交換. 不過它並不是像選擇排序法那樣直接進行交換, 而是通過相鄰交換的形式 : 在一次氣泡排序中, 相鄰元素進行比較, 如果左側的元素比右側的元素要大, 那麼進行交換

通過上述描述, 我們可以知道, 一次氣泡排序可以將最大的那個元素通過不斷交換, 最終讓其停頓在陣列的最後一個位置. 而氣泡排序法就是通過這樣不斷地 "冒出氣泡", 讓每一個元素被交換到對應的位置, 最終完成排序

在上面所演示的排序中, 只進行了一次氣泡排序就已經完成了, 這一次是讓陣列的第 1 個元素開始, 尋訪到第 n - 1 個元素, 然後相鄰的元素進行比較和交換. 接下來這一次是從第 1 個元素開始, 尋訪到第 n - 2 個元素. 因為此時第 n 個元素必定是最大的元素

void bubble_sort(int arr[], int size) {

    for(auto i {size}; i > 0; --i) {

        for(auto j {1}; j < i; ++j) {

            if(arr[j] < arr[j - 1]) {

                swap(arr[j], arr[j - 1]);

            }

        }

    }

}

在上面的 SVG 圖像中, 我們已經看出了一個問題 : 即時序列已經有序, 氣泡排序仍然會繼續, 直到所有的迴圈結束, 函式終結. 為了效率考慮, 如果檢測到序列已經有序, 那麼就應該即時終止排序. 因此, 我們仍然使用布林變數來實作. 我們發現, 如果某一個序列已經有序, 那麼不會發生任何交換, 此時就可以判定序列有序 :

void bubble_sort(int arr[], int size) {

    bool swapped {true};

    for(auto i {size}; i > 0 and swapped; --i) {

        swapped = false;

        for(auto j {1}; j < i; ++j) {

            if(arr[j] < arr[j - 1]) {

                swap(arr[j], arr[j - 1]);

                if(not swapped) {

                    swapped = true;

                }

            }

        }

    }

}

最後, 我們來討論氣泡排序的穩定性. 在對比的過程中, 我們發現, 若且唯若後面的元素比前面的元素小的時候, 才會發生交換. 我們簡單地考慮前後兩個元素相同的情況, 此時 arr[j] < arr[j - 1] 條件並不成立, 因此並不發生交換. 所以相同元素之間, 其前後排列並不發生改變. 因此, 氣泡排序法是穩定的