摘要訊息 : 元素如果像氣泡那樣慢慢從水底冒上來, 那麼也可以得到一個排序演算法.

0. 前言

在《【演算法】選擇排序法 (Selection Sort)》中的選擇排序法實際上是以交換為基礎的排序演算法, 每次選擇第 k 小的元素交換到第 k 個位置. 氣泡排序法也是以交換為基礎的排序演算法.

本篇文章中, 我們主要討論的是升序的氣泡排序法, 也就是從小到大對元素進行排序. 對於降序的情況, 類似可得.

更新紀錄 :

• 2022 年 4 月 22 日進行第一次更新和修正.

1. 氣泡策略

所謂氣泡策略, 指的是一個集合中最小的元素就像氣泡那樣從水底冒到水面上. 它並不像選擇排序法那樣直接通過搜尋和交換, 而是通過相鄰交換, 慢慢地讓最小的元素從集合的後面交換到集合的前面. 相鄰交換的具體做法是比較兩個相鄰的元素, 如果排在後面的元素比它前面的元素要小, 那麼交換這兩個元素. 交換從集合尾部開始.

我們可以發現, 如果在 Algorithm 1 中演算法發現了集合中最小的元素, 那麼它就會通過不斷交換來到 e_{1} 的位置.

例題 1. 設有集合 \mathscr {S} = \left \{ B, C_{1}, P, A, C_{2}, K \right \}, 對集合 \mathscr {S} 進行一次氣泡策略.

解 :

首先檢查 C_{2} 和 K, 有 C_{2} < K, 因此不交換. 檢查 A 和 C_{2}, 有 A < C_{2}, 因此不交換. 檢查 P 和 A, 有 P > A, 交換得到 \mathscr {S} = \left \{ B, C_{1}, A, P, C_{2}, K \right \}. 檢查 C_{1} 和 A, 有 C_{1} > A, 交換得到 \mathscr {S} = \left \{ B, A, C_{1}, P, C_{2}, K \right \}. 檢查 B 和 A, 有 B > A, 交換得到 \mathscr {S} = \left \{ A, B, C_{1}, P, C_{2}, K \right \}

\blacksquare

2. 氣泡排序法

對於一個集合不斷使用氣泡策略, 最終可以使得整個集合有序. 當進行第一次氣泡策略之後, 從氣泡策略的性質可以得到集合中第一個元素便是集合中最小的元素. 現在排除這個元素, 對集合中剩下的元素再使用氣泡策略. 不斷重複上述步驟, 直到集合中只剩下一個元素. 這個元素便是集合中最大的元素.

我們合稱 Algorithm 1 和 Algorithm 2 為氣泡排序法 (bubble sort).

3. 穩定性分析

我們在《【演算法】名次排序法 (Ranking Sort)》中引入了排序演算法穩定性的定義 (見定義 1). 現在我們來分析一下由 Algorithm 1 驅動的氣泡排序法是否是穩定的排序.

斷言 1. 由 Algorithm 1 驅動的氣泡排序法是穩定的排序演算法.

證明 :

設集合中有兩個相鄰且相等元素. 這兩個元素相等會使得 Algorithm 1 中 e_{i} < e_{i - 1} 不成立, 所以交換不會發生. 也就是說在任意情況下, 相鄰且相等元素的順序不會發生改變, 因此由 Algorithm 1 驅動的氣泡排序法是穩定的排序演算法.

\blacksquare

斷言 1 中並沒有直接斷言氣泡排序法就是穩定的演算法. 這是因為如果我們將 Algorithm 1 中的比較運算子換成 \leq 或者 \geq, 那麼就會破壞排序的穩定性. 當然, 那些在 \mathscr {S} 中相同的元素, 在 {\mathscr {S}}' 中是倒序排列的.

4. 即時終結的氣泡排序法

和選擇排序法類似, 如果在一次氣泡策略中沒有交換發生, 就說明集合中的元素是有序的. 因此, 一旦一次氣泡策略中沒有交換過元素, 那麼我們就可以即時終止排序演算法, 以提升演算法效能.

5. 複雜度分析

氣泡排序法在運作的過程中, 需要的輔助空間和集合中的元素數量無關, 因此其空間複雜度為 \Theta(1). 一次氣泡策略需要尋訪的元素數量為 O(n) 個, 非即時終止的氣泡排序法總共需要執行 n - 1 次氣泡策略, 所以非即時終止的氣泡排序法的時間複雜度是 (n - 1)O(n) = O(n^{2}). 對於即時終止的氣泡排序法, 在最好情況下的時間複雜度是 \Theta(n), 因為所有元素只都需要被尋訪一次. 在最壞的情況下, 時間複雜度仍然是 O(n^{2}). 因此, 在平均情況下, 即時終結的氣泡排序法的時間複雜度仍然是 \Theta(n^{2}).

6. 實作

#include <algorithm>

void bubble_sort(int arr[], int size) {
    for(auto i {size}; i > 0; --i) {
        bool swapped {};
        for(auto j {1}; j < i; ++j) {
            if(arr[j] < arr[j - 1]) {
                std::swap(arr[j], arr[j - 1]);
                if(not swapped) {
                    swapped = true;
                }
            }
        }
        if(not swapped) {
            break;
        }
    }
}

對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 bubble_sort 即可.