計數排序是一種線性時間的排序演算法。它不做任何元素之間的比較,而是靠「統計每個值出現了幾次」來決定排列結果,因此在特定條件下比所有基於比較的排序(O(n log n))都快。
計數排序是穩定排序。它額外開一個計數陣列 Count_arr,其中第 i 個元素的值,代表待排序陣列 Arr 中「值等於 i」的元素有幾個。有了這份統計,就能把每個元素放回正確位置。
1. 找出待排序陣列中的最大值與最小值,決定統計範圍。
2. 統計每個值 i 出現的次數,存入 Count_arr[i]。
3. 對 Count_arr 做累加(從第一項開始,每項加上前一項),得到每個值應該排在輸出陣列的哪個位置。
4. 反向遍歷原陣列:把元素 i 放到新陣列的第 Count_arr[i] 項,放完後把 Count_arr[i] 減 1。反向遍歷是為了保持相同元素的相對順序,也就是「穩定性」的來源。
/**
* 計數排序:非基於比較的排序演算法,
* 於 1954 年由 Harold H. Seward 提出。
* 對一定範圍內的整數排序時,複雜度為 O(n + k),
* 其中 k 是整數的範圍,快於任何比較排序演算法。
*/
function countSort(arr, min, max) {
var i, z = 0, count = [];
// 步驟 1:初始化計數陣列
for (i = min; i <= max; i++) {
count[i] = 0;
}
// 步驟 2:統計每個值出現的次數
for (i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
// 步驟 3 + 4:依序把值填回原陣列
for (i = min; i <= max; i++) {
while (count[i]-- > 0) {
arr[z++] = i;
}
}
return arr;
}
// 測試:產生 100 個 0~140 的隨機整數
var i, arr = [];
for (i = 0; i < 100; i++) {
arr.push(Math.floor(Math.random() * 141));
}
countSort(arr, 0, 140);
這裡做了個簡化:直接依值域从小到大把元素填回,省掉了累加與反向遍歷的步驟。代價是失去了穩定性——相同鍵值的元素順序可能改變。若需要穩定排序(例如先依姓名排、再依年齡排的多鍵排序場景),就必須照完整的四步驟走。
計數排序的威力來自它的前提:資料必須是非負整數,且值域 k 不能太大。複雜度 O(n + k) 意味著當 k 遠大於 n 時(例如排序 10 個介於 0 到 10^9 的數字),它會比 sort() 慢得多,而且會吃掉大量記憶體。
若遇到負數或浮點數,做法是「平移」與「縮放」:先減去最小值讓所有數變成非負整數,排序完再加回去。若是小數,可以乘以一個倍數轉成整數處理,但要小心精度問題。
實務上,一般的排序需求直接用原生 sort 就好:
var arr = [5, 2, 9, 1, 5, 6];
arr.sort(function (a, b) { return a - b; }); // [1, 2, 5, 5, 6, 9]
而計數排序真正的用武之地,是實作「依出現頻率排序」這類需求——那時你需要本來就要統計次數,計數排序的思路正好順勢完成排序。例如:
function frequencySort(arr) {
var count = new Map();
arr.forEach(function (v) { count.set(v, (count.get(v) || 0) + 1); });
return arr.slice().sort(function (a, b) {
return count.get(b) - count.get(a); // 依出現次數遞減
});
}
演算法的價值在於理解「用空間換時間」這個取捨。知道計數排序的存在,遇到合適場景時能想到它,這比背下實作更重要。