計數排序與排序的極限

只靠比較，最快能多快

第 06～08 課的排序（選擇、插入、氣泡、合併、快速）有一個共同點：它們只靠「比較兩個元素誰大」來決定順序。 最快的合併排序是 O(n log n)。有沒有可能更快？

這一課分成三部分：

1. 不用比較的排序：如果資料是範圍不大的整數，例如 0～100 分的成績，可以直接數每個分數有幾個人，O(n + k) 就排好（k 是值的範圍）
2. 比較排序的極限：只靠比較的話，任何方法在最壞情況下都至少要比較約 n log₂n 次，合併排序已經達到這個等級
3. 用好內建排序：實際寫程式時幾乎都用語言內建的排序，重點是會依多個條件排序、寫對比較函數，以及知道它穩不穩定

計數排序：先數一數，再依序寫回去

假設要排序的都是 0～5 的整數。準備一個長度 6 的陣列 count，count[v] 記錄「值 v 出現幾次」：

1. 掃一遍資料，每看到一個 x，就把 count[x] 加 1
2. 從 v = 0 到 5，值 v 出現幾次，就依序寫幾個 v 到輸出

整個過程沒有任何兩個元素互相比較。第 1 步掃 n 個元素，第 2 步走過 k 個可能的值、總共寫出 n 個元素，所以是 O(n + k)，額外空間也是 O(n + k)。

在動畫裡，count 陣列下方的索引就是「值」，格子裡是「出現次數」。

計數排序的限制

計數排序很快，但有明確的使用條件：

適合的例子：考試成績（0～100）、年齡、年份、某一位數字（0～9）。不適合的例子：任意的浮點數、很長的字串、範圍很大的身分證字號。

上面的寫法直接寫出「值」，只適合排序整數本身。如果要排序的是帶有其他資料的紀錄（例如依分數排序學生）， 要改用累加計數：把 count 累加起來，count[d] 就變成「鍵 ≤ d 的共有幾個」，也就知道鍵為 d 的最後一筆該放在哪個位置。 從資料的最後一筆往前放，鍵相同的紀錄會維持原本的先後，所以這個寫法是穩定的。下一個範例就是這種寫法。

基數排序：一位數一位數排

三位數的範圍是 0～999，count 要開 1,000 格。換個想法：每次只看一位數（0～9，只要 10 格），從個位數排起：

1. 依個位數排序
2. 依十位數排序
3. 依百位數排序

排完百位數，整個陣列就排好了。這叫做 LSD 基數排序（least significant digit first，從最低位開始的基數排序）。

關鍵在於每一輪都必須是穩定的排序。例如 329 和 355 的百位數都是 3，排百位數時兩者「平手」； 穩定的排序會保留上一輪（依十位數）排出的先後，329 在 355 前面，結果才正確。

取出某一位數：x // exp % 10（C++、Java 寫 x / exp % 10），exp 依序是 1、10、100。 d 位數的資料要排 d 輪，每輪 O(n + 10)，總共 O(d × n)。

比較排序的下限：為什麼不可能比 n log n 更快

計數排序之所以能突破 O(n log n)，是因為它直接用值當索引，不是靠比較。只靠比較的排序，有一個無法突破的下限，可以這樣理解：

1. n 個不同的元素，有 n! 種可能的排列順序（3 個元素有 3 × 2 × 1 = 6 種）。排序演算法必須能分辨出輸入是哪一種，因為每一種需要不同的搬動方式。
2. 每比較一次（a < b 嗎？），只能得到「是」或「否」，把可能性分成兩邊。
3. 把所有可能的比較過程畫成一棵樹（決策樹）：每個內部節點是一次比較，往左是「是」、往右是「否」，每片葉子是一種確定的排列。 比較 k 次之後，最多只能分出 2ᵏ 種不同的結果。
4. 要分辨 n! 種排列，至少需要 2ᵏ ≥ n!，也就是最壞情況下至少要比較約 log₂(n!) 次（決策樹的高度）。

log₂(n!) 和 n log₂n 是同一個等級（n! 大約是 n 個「接近 n 的數」相乘），所以任何比較排序的最壞情況都至少是 Ω(n log n)。 這裡的 Ω 表示「至少是這個等級」。合併排序最壞是 O(n log n)，已經達到這個下限，在「只靠比較」的前提下不可能有等級上更好的方法。

下面的程式對 n = 1～10 算出「2ᵏ 第一次超過 n! 的 k」，也就是最壞情況至少要比較幾次。

用好內建排序：依多個條件排序

實際寫程式時，幾乎都直接用語言內建的排序，它們都是 O(n log n)，而且經過大量最佳化。要學的是怎麼告訴它依什麼排。

Python：用 key 指定「每個元素拿什麼來比」；回傳元組（tuple）就會依序比較每個欄位。數字欄位要由大到小時加負號：

students.sort(key=lambda s: (-s[1], s[0]))        # 分數由高到低，同分依名字

C++：傳入比較函數（常用 lambda），x 應該排在 y 前面時回傳 true。一定要用嚴格的 < 或 >，不能用 <=，否則 std::sort 的行為未定義：

sort(v.begin(), v.end(), [](const Student& x, const Student& y) {
    if (x.score != y.score) return x.score > y.score;   // 分數高的在前
    return x.name < y.name;                             // 同分依名字
});

Java：傳入 Comparator，回傳負數表示 x 在前、0 表示相等、正數表示 y 在前。用 Integer.compare 而不是 x - y，避免相減時溢位：

list.sort((x, y) -> {
    if (x.score() != y.score()) return Integer.compare(y.score(), x.score());
    return x.name().compareTo(y.name());
});

下面的範例用整數示範：先只依個位數排序，再加上「個位數相同時比數字本身」的第二個條件。

哪些內建排序是穩定的

在 C++ 裡，需要「相同鍵維持原本順序」時要用 stable_sort。std::sort 在資料少時常常剛好維持原順序，但標準沒有保證，資料一多就可能打亂，這類錯誤很難發現。

穩定排序有一個實用的技巧：依多個條件排序時，可以從次要條件排到主要條件。 例如先依名字排一次，再依分數（由高到低）穩定地排一次，結果就是「分數高的在前，同分依名字」，和用元組或比較函數一次排好相同：

students.sort(key=lambda s: s[0])                  # 次要條件：名字
students.sort(key=lambda s: s[1], reverse=True)    # 主要條件：分數（穩定，同分保留名字的順序）

這和基數排序先排個位、再排十位是同一個道理。

重點整理

• 計數排序：數出每個值出現幾次再依序寫回，O(n + k)；只適用於整數且範圍 k 不大
• 用累加計數並從後往前放，計數排序就是穩定的，可以排序帶有其他資料的紀錄
• LSD 基數排序：從最低位排到最高位，每一輪用穩定的計數排序，d 位數共 O(d × n)
• 比較排序的下限：n! 種排列、每次比較只能分成兩邊，所以最壞至少要約 log₂(n!) 次，也就是 Ω(n log n)；合併排序已經達到這個等級
• 內建排序：Python 用 key（元組可依多個欄位）、C++ 用回傳 bool 的比較函數（嚴格的 <）、Java 用 Comparator（Integer.compare）
• Python 的排序、Java 的物件排序保證穩定；C++ 的 std::sort 不保證，要穩定請用 std::stable_sort

下一課：堆疊與佇列。從排序換到資料結構，看「後進先出」和「先進先出」兩種存取規則能解決哪些問題。