11.11 計數排序法

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

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

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

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

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