Sorting · 01 / 09

Bubble Sort氣泡排序

相鄰交換，最直覺但最慢。

用在：教學用，理解「相鄰交換」與穩定性

時間複雜度O(n²)

空間複雜度O(1)

難度入門

前置知識Array & Dynamic Array、Big-O Notation

01為什麼需要它

十幾筆資料，程式要寫在紙上

白板面試或嵌入式的小裝置，要把一小串數字排好，沒有函式庫可以呼叫，也不想寫遞迴。

為什麼用它氣泡排序只有兩層迴圈和一個交換，五行寫完、不會寫錯，資料只有幾十筆時 O(n²) 完全無所謂。它是理解「排序」這件事最短的路。

資料幾乎排好了，只想確認一下

每天更新一次的排行榜，昨天已經有序，今天只有一兩個人名次動了，想用最少的力氣修好。

為什麼用它加上「一整輪都沒交換就停」的檢查，已排序的資料只掃一遍就結束，O(n)。只有一個人名次變差（位置太前面）時，一輪就把他推回去；但名次變好的人（位置太後面）每輪只能往前一格，差 d 名就得跑 d 輪。最後一名衝到第一名，照樣要跑滿 n−1 輪、O(n²)，這種資料改用插入排序更穩。

理解「穩定排序」與「交換次數」

排序後同分的人順序不能亂；或者每次交換要寫入很慢的儲存體，想知道到底交換了幾次。

為什麼用它氣泡排序只交換相鄰且嚴格大於的元素，同值永遠不會互換，天生穩定；交換次數正好等於資料裡的逆序對數量，這也是「只准交換相鄰元素」時最少需要的次數。它是講清楚這兩個概念的教學範本；真的在意寫入次數，就改用最多只交換 n−1 次的選擇排序。

看到這些關鍵字就想到它：相鄰交換、每輪推出一個最大值、幾乎有序想早點停、逆序對數量、教學或小資料。

02核心概念

氣泡排序的規則只有一條：從左到右看每一對相鄰元素，左邊比右邊大就交換。一輪掃完，目前的最大值一定被一路帶到最右邊，像氣泡浮到水面。這個位置從此固定，下一輪只掃前面 n−1 格，再下一輪掃 n−2 格，最多 n−1 輪就全部排好。

為什麼正確？每一輪結束時，「還沒固定的區域」裡的最大值必定被推到該區域的尾端，因為一旦掃到它，它和右邊的元素比都不會輸，會一路往右換（遇到一樣大的，就由右邊那個接棒繼續往右）。所以第 i 輪結束後，尾端 i 個元素是整體最大的 i 個且已排好。歸納到 n−1 輪就完成。

複雜度：第 i 輪（從 1 算起）做 n−i 次比較，加總 (n−1)+(n−2)+…+1 = n(n−1)/2，O(n²)。交換次數等於逆序對的數量（每次交換恰好消掉一對相鄰逆序），最壞（完全反序）也是 n(n−1)/2，最好（已有序）是 0。加上 swapped 旗標，已有序的輸入一輪就結束，最好情況變成 O(n)；平均與最壞仍是 O(n²)。要跑幾輪不看「亂掉的元素有幾個」，而看「最需要往左移的元素要移幾格」：每一輪，左邊還有更大值的元素都恰好往左移一格。額外空間 O(1)。

和相鄰演算法的比較：選擇排序比較次數固定但交換最多 n−1 次；插入排序的成本是 O(n + 逆序對數)，只要逆序對少就接近 O(n)，不怕小值卡在尾端，而且每次只做「搬移」不做完整交換，常數更小，所以實務上小陣列都用插入排序而不是氣泡排序。氣泡排序的價值在教學：它把「交換相鄰元素」「穩定性」「逆序對」三個概念一次講清楚。

03演算法步驟

1外層迴圈 i 從 0 到 n−2，代表第 i+1 輪；每輪開始把 swapped 設為 False。
2內層 j 從 0 掃到 n−2−i：比較 a[j] 與 a[j+1]，左邊大就交換並把 swapped 設為 True。
3這一輪結束，a[n−1−i] 是本輪最大值，固定不動；之後的輪次不再看它。
4若 swapped 仍是 False，代表這一輪沒有任何逆序對，陣列已經有序，提前結束。
5要穩定就只在「嚴格大於」時交換；用 >= 會讓同值元素互換位置，穩定性就沒了。

04互動示範

共用陣列 [5, 2, 9, 1, 7, 3, 8, 4]。每一步是一次相鄰比較，交換時兩格變藍色。注意每輪結束尾端多固定一格（綠色），以及第五輪沒有任何交換就直接停下。

開始[5, 2, 9, 1, 7, 3, 8, 4] · 由小到大

陣列

52917384

黃色是正在比較的兩格（沒交換），藍色是比較後交換了的兩格，綠色是已固定的尾端

比較次數

交換次數

已固定

0 / 8

步驟 0/31從左到右比較相鄰兩格，大的往右換。每掃完一輪，目前最大的那個一定被推到尾端，尾端就固定了。

05程式碼

基本版加上提前結束，以及雙向掃描的雞尾酒排序變形。雞尾酒排序解決「小值在最尾端要 n−1 輪才回到前面」的問題（所謂的烏龜），但它只改善這類資料，最壞仍是 O(n²)。

# 氣泡排序：相鄰兩格比較，大的往右換
# 每掃完一輪，這輪最大的元素一定被推到尾端
def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):          # 尾端 i 個已固定，不用再看
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                      # 一整輪沒交換，代表已經有序
            break
    return a


# 變形：雞尾酒排序（雙向氣泡）
# 一輪往右推最大值、一輪往左推最小值。小值卡在尾端（烏龜）時快很多，
# 但最壞仍是 O(n²)：完全反序時比較次數和氣泡排序一樣
def cocktail_sort(a):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        swapped = False
        for j in range(lo, hi):             # 往右推最大
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        hi -= 1
        for j in range(hi, lo, -1):         # 往左推最小
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]
                swapped = True
        lo += 1
        if not swapped:
            break
    return a


if __name__ == "__main__":
    print(bubble_sort([5, 2, 9, 1, 7, 3, 8, 4]))     # [1, 2, 3, 4, 5, 7, 8, 9]
    print(cocktail_sort([5, 2, 9, 1, 7, 3, 8, 4]))   # [1, 2, 3, 4, 5, 7, 8, 9]

06練習題

LeetCode 1051Height Checker（排序後比對有幾個位置不同）Easy
LeetCode 2717Semi-Ordered Permutation（最少相鄰交換次數，就是把 1 和 n 冒泡到兩端）Easy
LeetCode 283Move Zeroes（把 0 當最大值做穩定的相鄰交換，再想想雙指標怎麼做到 O(n)）Easy
LeetCode 75Sort Colors（三種值，想想能不能比 O(n²) 更好）Medium
LeetCode 3011Find if Array Can Be Sorted（只准交換 1 的位元數相同的相鄰元素，直接模擬氣泡排序）Medium
LeetCode 912Sort an Array（用 O(n²) 會超時，體會一下差距）Medium

上一篇—下一篇Selection Sort