排序演算法那麼多，你真正需要搞懂的只有三個半：Quick Sort、Merge Sort、Insertion Sort，還有半個 Bubble Sort（用來面試解釋「什麼是穩定排序」）。
先講結論
一般情況用 Quick Sort，需要穩定排序用 Merge Sort，資料量小或幾乎排好了用 Insertion Sort。Bubble Sort 和 Selection Sort 基本上只存在於教科書裡。
| 演算法 | 時間(平均) | 時間(最差) | 空間 | 穩定 |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | 是 |
| Selection Sort | O(n²) | O(n²) | O(1) | 否 |
| Insertion Sort | O(n²) | O(n²) | O(1) | 是 |
| Merge Sort | O(n log n) | O(n log n) | O(n) | 是 |
| Quick Sort | O(n log n) | O(n²) | O(log n) | 否 |
穩定性是什麼？兩個值相同的元素，排序後相對位置不變。聽起來無關緊要？等你需要「先按價格排，同價格按上架時間排」的時候就知道了。
O(n²) 三兄弟：能跑，但跑不遠
Bubble Sort 像泡泡一樣，大的往上浮。每一輪把相鄰的比一比、該交換就交換。
[64, 34, 25, 12]
第一輪：64>34 換 → 64>25 換 → 64>12 換 → [34, 25, 12, 64]
第二輪：34>25 換 → 34>12 換 → [25, 12, 34, 64]
第三輪：25>12 換 → [12, 25, 34, 64]
Selection Sort 每次找最小的放前面。直覺好懂，但不穩定（交換會打亂相同元素的順序）。
Insertion Sort 像整理撲克牌，一張一張插到對的位置。它有個被低估的超能力：資料近乎有序時是 O(n)。所以 Tim Sort（Python/Java 內建排序）在小區段就是用 Insertion Sort。
[64] | 34, 25, 12 → 插入 34 → [34, 64]
[34, 64] | 25, 12 → 插入 25 → [25, 34, 64]
[25, 34, 64] | 12 → 插入 12 → [12, 25, 34, 64]
Merge Sort：穩定的好學生
分而治之：拆到只剩一個元素，再兩兩合併。
[64, 34, 25, 12]
↓ 分割
[64, 34] [25, 12]
↓ ↓
[64] [34] [25] [12]
↓ ↓ 合併
[34, 64] [12, 25]
↓ 合併
[12, 25, 34, 64]
合併過程是整個演算法的精髓——兩個已排序的陣列，用兩根指標從頭比，小的先放，O(n) 搞定。
代價是什麼？需要 O(n) 額外空間。在記憶體很貴的場景（嵌入式系統之類），這可能是個 deal breaker。
Quick Sort：實務之王
選一個 pivot，小的放左邊，大的放右邊，遞迴處理。
[64, 34, 25, 12, 22, 90] pivot = 22
小於 22：[12]
大於 22：[64, 34, 25, 90]
結果：[12, 22, ...] 繼續遞迴
為什麼最差 O(n²) 卻還是「實務上最快」？三個原因：
- 原地排序，cache 友好（Merge Sort 需要來回複製）
- 常數因子小（每步操作簡單）
- 平均 O(n log n)，最差情況可以用隨機 pivot 或三數取中避免
所以面試官問你「為什麼不直接用 Merge Sort」的時候，你可以回答：「因為 cache locality。」然後看他露出滿意的微笑。
怎麼選？
小資料（< 50）或近乎有序 → Insertion Sort 需要穩定排序 → Merge Sort 一般情況 → Quick Sort 記憶體受限 → Quick Sort（原地排序）
其他更特殊的排序（Heap Sort、Radix Sort、Counting Sort）請看 更多排序演算法。
Bubble Sort 唯一的用途是讓你在面試時說：「我知道它很慢，但它是穩定的。」然後優雅地轉向 Quick Sort。