上一篇講了五個基礎排序。這篇講的是「特殊場景的排序」——當你的資料有特殊性質時，可以比 O(n log n) 更快。以及 Tim Sort，你每天都在用但可能不知道的排序演算法。
先講結論
比較排序的理論下界是 O(n log n)，沒辦法更快了。但如果你的資料是整數、值域不大、或均勻分佈，非比較排序可以做到 O(n)。
| 演算法 | 時間 | 空間 | 穩定 | 適用 |
|---|---|---|---|---|
| Heap Sort | O(n log n) | O(1) | 否 | 記憶體受限 |
| Counting Sort | O(n + k) | O(k) | 是 | 整數，值域小 |
| Radix Sort | O(d(n+k)) | O(n+k) | 是 | 整數，位數固定 |
| Bucket Sort | O(n + k) | O(n) | 是 | 均勻分佈 |
| Shell Sort | O(n^1.3) | O(1) | 否 | 中等規模 |
| Tim Sort | O(n log n) | O(n) | 是 | 通用（內建排序） |
| Cocktail Sort | O(n²) / O(n) best | O(1) | 是 | 幾乎有序、Bubble 改良 |
| Comb Sort | O(n log n) avg | O(1) | 否 | Bubble 的間隔版 |
| Cycle Sort | O(n²) | O(1) | 否 | 寫入次數最少 |
| Introsort | O(n log n) | O(log n) | 否 | C++ STL 的選擇 |
Heap Sort：空間最省的 O(n log n)
利用 max heap 的性質：根節點永遠最大。每次取出根（最大值）放到陣列尾端，再調整堆。
void heapSort(int[] arr) {
int n = arr.length;
for (int i = n/2-1; i >= 0; i--)
heapify(arr, n, i); // 建堆 O(n)
for (int i = n-1; i > 0; i--) {
swap(arr, 0, i); // 最大值放後面
heapify(arr, i, 0); // 調整 O(log n)
}
}O(1) 額外空間，但 cache locality 差（heap 的存取模式跳來跳去），所以實務上比 Quick Sort 慢。什麼時候用？記憶體極度受限或需要保證最差 O(n log n)（Quick Sort 最差是 O(n²)）。
Counting Sort：不比較，純計數
如果值域是 0~k，開一個大小 k 的陣列統計每個值出現幾次，然後按順序輸出。
[4, 2, 2, 8, 3, 3, 1]
count: [0, 1, 2, 2, 1, 0, 0, 0, 1]
結果: [1, 2, 2, 3, 3, 4, 8]
O(n + k)。但如果值域很大（比如排序身分證字號），開不了那麼大的陣列。
Radix Sort：按位數排
從低位到高位，每一位用 Counting Sort。
[170, 45, 75, 90, 802, 24, 2, 66]
按個位: [170, 90, 802, 2, 24, 45, 75, 66]
按十位: [802, 2, 24, 45, 66, 170, 75, 90]
按百位: [2, 24, 45, 66, 75, 90, 170, 802]
O(d × (n + k))，d 是位數。適合整數且位數固定的場景。
Bucket Sort：分桶再排
把數據分到幾個桶裡，每個桶內部排序，再合併。
如果數據均勻分佈，每個桶裡的元素很少，桶內排序幾乎是 O(1)，整體接近 O(n)。不均勻的話就退化成 O(n²)。
Tim Sort：你一直在用的排序
Python 的 sort() 和 Java 的 Arrays.sort()（Object 版）用的就是 Tim Sort。
核心想法：現實世界的資料很少是完全亂序的，通常有一些「已排序的片段」。Tim Sort 先找出這些片段（run），小片段用 Insertion Sort，再用 Merge Sort 合併。
- 近乎有序？O(n)
- 一般情況？O(n log n)
- 穩定？是
所以你不需要自己挑排序演算法——語言內建的已經幫你選了 Tim Sort。除非你有特殊需求（整數值域小 → Counting Sort、記憶體受限 → Heap Sort），否則直接 .sort() 就好。
Cocktail Sort：雙向 Bubble
Bubble Sort 每輪只從左掃到右——大的很快浮右邊（兔子），但小的從右往左移極慢（烏龜）。Cocktail Sort 每輪來回掃，一次把最大值推右、最小值推左，烏龜一輪就能歸位。
[5, 1, 4, 2, 8, 0, 2]
→ 左到右：8 到底 [1, 4, 2, 5, 0, 2, 8]
← 右到左：0 到頭 [0, 1, 4, 2, 5, 2, 8]
→ 縮小範圍繼續...
穩定、原地。複雜度跟 Bubble Sort 一樣是 O(n²)，但幾乎有序時快一些。
Comb Sort：梳子梳掉烏龜
Cocktail Sort 每次只移動一格，根治不了問題。Comb Sort 的想法更像 Shell Sort：從大間隔開始比較，把遠端的烏龜提前消滅，間隔每輪縮小 1.3 倍，最後 gap=1 時等同 Bubble Sort，但此時幾乎已沒有烏龜。
int gap = arr.length;
boolean swapped = true;
while (gap > 1 || swapped) {
gap = Math.max(1, (int)(gap / 1.3));
swapped = false;
for (int i = 0; i + gap < arr.length; i++)
if (arr[i] > arr[i + gap]) { swap(i, i+gap); swapped = true; }
}不穩定，平均接近 O(n log n)，實作極簡單。競賽中偶爾用來替代 Bubble Sort。
Cycle Sort：寫入次數最少
每個元素找到它的正確位置（比它小的元素有幾個），直接放過去。這樣每個元素最多被寫入一次，整個排序的寫入次數是 O(n)。
為什麼重要？快閃記憶體（NAND Flash）每個位置的寫入壽命有限，寫入次數少 = 硬體壽命更長。時間複雜度 O(n²)，不穩定，原地。你不會在一般情景用它，但硬體相關的排序場景會碰到。
Introsort：C++ 的選擇
C++ 的 std::sort 用的是 Introsort，而不是 Tim Sort。原因是它更適合原始型別（int、double）——不需要穩定性，只要快。
策略：用 Quick Sort 起手（最快），遞迴深度超過 2×log₂(n) 就切換到 Heap Sort（防止最差情況），子陣列小於 16 個元素改用 Insertion Sort（小陣列開銷最低）。
Quick Sort → 深度過深? → Heap Sort
子陣列夠小? → Insertion Sort
保證 O(n log n) 最差情況，O(log n) 額外空間，不穩定。Java/Python 內建用 Tim Sort（穩定）；C++ 用 Introsort（快）。兩個選擇都是對的，只是優先考量不同。
怎麼選？
你的資料是什麼？
├─ 整數，值域小 → Counting Sort
├─ 整數，位數固定 → Radix Sort
├─ 浮點數，均勻分佈 → Bucket Sort
└─ 通用資料
├─ 記憶體極度受限 → Heap Sort
├─ 幾乎有序，需要穩定 → Tim Sort / Cocktail Sort
├─ 幾乎有序，不需穩定 → Comb Sort
├─ 寫入代價高（Flash）→ Cycle Sort
└─ 一般情況 → Quick Sort / 直接 .sort()
最好的排序演算法是什麼？答：你語言內建的那個。Tim Sort（Java/Python）和 Introsort（C++）已經幫你做了所有決策。除非你在面試或有硬體限制，否則請直接用 .sort()。