非比較排序：怎麼比 O(n log n) 還快？

一個重要事實

所有「兩兩比較大小」的排序演算法，最壞情況下限是 O(n log n)。（這有嚴格證明——決策樹至少有 n! 個葉節點，樹高 ≥ log(n!) = Ω(n log n)。）

那要怎麼比 O(n log n) 還快？ 答案：不要比較。

Counting Sort：直接數

想像你在開家長日。100 位學生報到，年齡 6~12 歲。怎麼排出最年輕到最年長？

「拿張紙列出 6, 7, 8, 9, 10, 11, 12，每報一個就在那一格畫一筆」——數完直接照順序唸出來。

Pseudocode

Algorithm CountingSort(A, n, k):

count ← [0] × (k+1)

for x in A:

count[x] ← count[x] + 1 // O(n)

idx ← 0

for v ← 0 to k:

for j ← 1 to count[v]:

A[idx] ← v; idx ← idx + 1 // O(n + k)

時間：O(n + k)，k = 值域範圍。

⚠️什麼時候用 / 什麼時候不能用

✅ 適用：值域小（k 約等於 n）。例如：年齡 0~~150、考試分數 0~~100。 ❌ 不適用：值域大（k 遠大於 n）。例如：員工編號可能 0~10⁹，要開 10 億格陣列，記憶體爆。 ❌ 不適用：浮點數、字串（無自然整數對應）。

Radix Sort：一位數一位數來

要排 [170, 45, 75, 90, 802, 24, 2, 66]——值域 0~~999，counting sort 要開 1000 格還行。但 0~~99999999 就不行了。

Radix Sort 的點子：從個位數開始，用 counting sort 排個位 → 排十位 → 排百位…

原始：     170, 045, 075, 090, 802, 024, 002, 066

按個位排：170, 090, 002, 802, 024, 045, 075, 066
         (0)  (0)  (2)  (2)  (4)  (5)  (5)  (6)

按十位排：002, 802, 024, 045, 066, 170, 075, 090
         (0)  (0)  (2)  (4)  (6)  (7)  (7)  (9)

按百位排：002, 024, 045, 066, 075, 090, 170, 802
         (0)  (0)  (0)  (0)  (0)  (0)  (1)  (8)
                                                ✓

為什麼這樣可以？ 因為 counting sort 是穩定的——按低位排完後，相同高位的元素相對順序不變，這樣最終結果就會按整數大小排好。

時間：O(d × (n + k))，d = 位數，k = 每位的值域（通常是 10）。位數固定的話 → O(n)。

💡超越 O(n log n) 的祕密

比較排序的 O(n log n) 下限只適用於「兩兩比較」。 Counting / Radix 都是「讀值、放桶子」，不算比較，所以不受限。

代價：只能排能「映射到桶子」的東西——整數、固定長度字串。浮點數、自訂物件就沒辦法。

複雜度比較

演算法	時間	空間	穩定	限制
Counting Sort	O(n + k)	O(n + k)	是	值域 k 不能太大
Radix Sort	O(d × (n + k))	O(n + k)	是	要能拆位
Quick Sort	O(n²) 最壞	O(log n)	否	—
Merge Sort	O(n log n)	O(n)	是	—

📝考試會這樣考

題型一：跑一遍 Counting Sort。 給陣列和值域，列出 count 陣列和最終結果。

題型二：跑一遍 Radix Sort。 給整數陣列，列出每一輪（按個/十/百位）後的狀態。

題型三：為什麼能比 O(n log n) 快？ 答：因為不使用比較操作——比較排序的下限證明不適用。

題型四：什麼時候不該用 Counting Sort？ 答：當值域 k 遠大於 n 時，空間 O(n + k) 變成主要成本。

題型五：Radix Sort 為什麼必須用穩定排序當子程序？ 答：要保證相同位元的元素相對順序不變，這樣低位排好的結果才不會被高位排序破壞。

這章記住

比較排序最壞下限是 O(n log n)。
不比較就沒這個下限——Counting Sort 和 Radix Sort 利用「桶子」思想。
Counting Sort O(n + k)，限制是值域 k 不能太大。
Radix Sort O(d × n)，底層必須用穩定排序（通常是 Counting Sort）。