氣泡排序：泡泡浮上來（附動畫）

想像你在排撲克牌

桌上有一排牌：[5, 3, 8, 1, 4]，你要從小到大排好。

氣泡排序的做法：從最左邊開始，兩兩比較，比較大的往右擠。每跑完一輪，最大的那張就會浮到最右邊（像泡泡浮上水面）。

直接看動畫

準備好了

按「開始」播放動畫。粉紅色 = 正在比較。

按一下「開始」，看著大數字怎麼一步一步「冒泡」到右邊。

一輪一輪拆給你看

以 [5, 3, 8, 1, 4] 為例：

第 1 輪（最大的 8 要冒到最右邊）：

動作	陣列
比 5 和 3，5 大，換	[3, 5, 8, 1, 4]
比 5 和 8，沒事	[3, 5, 8, 1, 4]
比 8 和 1，8 大，換	[3, 5, 1, 8, 4]
比 8 和 4，8 大，換	[3, 5, 1, 4, 8]

最大的 8 已經到底了。✨

第 2 輪（5 要冒到倒數第二）：

動作	陣列
比 3 和 5，沒事	[3, 5, 1, 4, 8]
比 5 和 1，5 大，換	[3, 1, 5, 4, 8]
比 5 和 4，5 大，換	[3, 1, 4, 5, 8]

5 到位了。

第 3 輪：[1, 3, 4, 5, 8] ← 排完了。

💡關鍵直覺

每跑完一輪，最右邊就多一個排好的。所以 n 個元素最多跑 n-1 輪就排完。

寫成 Pseudocode

Algorithm BubbleSort(A, n):

for i ← 0 to n-2: // 跑幾輪

for j ← 0 to n-2-i: // 每輪兩兩比較

if A[j] > A[j+1]:

swap(A[j], A[j+1])

讀法：

外層 i：跑第幾輪。
內層 j：在這一輪裡兩兩比較。
n-2-i 的意思是：右邊已經排好的部分不用再比（節省時間）。

複雜度分析

外層 n 次，內層平均 n/2 次 → O(n²)。

情境	比較次數	Big-O
最壞（完全反向）	n(n-1)/2 ≈ n²/2	O(n²)
平均	也差不多 n²/2	O(n²)
最好（已排好）	n-1 次（加 early-stop 才行）	O(n)

⚠️氣泡排序的真相

它非常慢。n=10000 就要跑一億次。 那為什麼還要學？ 因為：

考試一定會考。
它是「雙層 for 迴圈排序」的代表，看懂它再看選擇/插入排序會很快。
Code 短到可以背起來。

一個小優化：提早收工

如果某一輪都沒換過，代表已經排好了，可以直接結束：

Algorithm BubbleSort(A, n):

for i ← 0 to n-2:

swapped ← false

for j ← 0 to n-2-i:

if A[j] > A[j+1]:

swap(A[j], A[j+1])

swapped ← true

if not swapped: break

加了這個，已排序的陣列只跑一輪就結束，最佳情況變 O(n)。

📝考試會這樣考

題型一：給陣列，畫出每一輪的結果。

例：用 Bubble Sort 排 [4, 2, 7, 1, 3]，列出每輪結束後的陣列。

怎麼下筆：畫表格，標清楚「第幾輪」。

輪次	陣列狀態
初始	[4, 2, 7, 1, 3]
第 1 輪後	[2, 4, 1, 3, 7]
第 2 輪後	[2, 1, 3, 4, 7]
第 3 輪後	[1, 2, 3, 4, 7]
第 4 輪後	[1, 2, 3, 4, 7]

注意：每輪「最後一個元素已就位」要標出來（粗體 / 底線都行），改卷老師看了會很開心。

題型二：問最壞情況做幾次比較。 n 個元素 → 比較次數 = n(n-1)/2 = (n²-n)/2。代入 n=5 就是 10 次。

題型三：問為什麼最好情況是 O(n)。 答：加了「沒換就停」優化後，已排序的陣列只跑一輪、做 n-1 次比較、零次交換就結束。

這章記住三件事

Bubble Sort = 兩兩比較、大的往右擠，跑 n-1 輪。
時間複雜度 O(n²)，慢但簡單，考試常考追蹤過程。
加「sw apped 旗標」可以讓最好情況變 O(n)。

下一章看插入排序——你打牌時整理手牌的方式。