11.11 計數排序法

泡沫排序靠「比較」排序。接下來這招完全不同——從頭到尾不比較任何兩個數，照樣把資料排好。

¶原理：數出現次數，再依序倒出來

如果要排序的數字範圍不大——比如全是 0 \sim 100 的分數——可以這樣做：

1. 開一個計數陣列 cnt，大小蓋過整個值域。
2. 讀入每個數 x 就執行 cnt[x]++——「x 又出現一次」。
3. 由小到大掃過整個值域：數值 v 出現幾次，就輸出幾個 v。

輸出天生就是由小到大——因為我們是按順序掃過值域的。這就是計數排序法（Counting Sort）。你其實見過它的前半段：上冊 6.7 的計數陣列統計分數，當時統計完就收工；計數排序只是多做第 3 步，把統計結果依序倒出來。

#include <iostream>
using namespace std;

const int MAX_V = 1000000;     // 值域上限
int cnt[MAX_V + 1];            // cnt[v]＝數值 v 出現的次數（全域：自動全 0）

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;              // 「登記」一次 x
    }

    // 由小到大掃過整個值域：v 出現幾次就印幾個 v
    for (int v = 0; v <= MAX_V; v++) {
        while (cnt[v] > 0) {
            cout << v << ' ';
            cnt[v]--;
        }
    }
    cout << '\n';
    return 0;
}

執行結果（輸入 5 與 3 1 4 1 5）：

1 1 3 4 5

¶快，但挑食

計數排序的運算量是 O(n + V)，其中 V 是值域大小（陣列要掃 V + 1 格、資料讀 n 個）——連 \log 都沒有，值域小的時候比 sort 還快。但它非常挑食：

再從思維的角度看一眼：8.2 把字元當成整數運算、10.9 把數字當字串拆位——計數排序則是把數字當索引：數值不再只是「被處理的資料」，它直接指出「該住進陣列的哪一格」。這個「拿數值當格子編號」的腦洞，之後在更進階的資料結構裡會一用再用，計數排序是它最漂亮的第一課。

動手試試看：把範例改成由大到小輸出（第 3 步的掃描方向反過來就好）。再想想：如果輸入可能是 -100 \sim 100，程式要怎麼改？動手把「平移」寫出來，拿幾筆含負數的輸入驗證。