氣泡排序：泡泡浮上來（附動畫）
第一個排序演算法。看到動畫你就懂為什麼叫「氣泡」。慢，但是好懂、好寫、考試常考。
- 給你陣列，畫出每一輪 bubble sort 後的狀態（題目最常見）
- 最壞情況做幾次比較？ n(n-1)/2，會代入 n=5 算出 10
- 為什麼最好情況可以 O(n)？ 加 swapped flag 後已排序的陣列只跑一輪 看完這章你就會解這三類。
想像你在排撲克牌
桌上有一排牌：[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
讀法：
- 外層
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 短到可以背起來。
一個小優化：提早收工
如果某一輪都沒換過，代表已經排好了，可以直接結束：
加了這個，已排序的陣列只跑一輪就結束，最佳情況變 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 排 [4, 2, 7, 1]，第 1 輪結束後是什麼？
下一章看插入排序——你打牌時整理手牌的方式。
學習進度只存在你的瀏覽器，不會上傳。