計數排序 是非比較型線性排序算法,適用於已知範圍的整數排序。時間複雜度 O(n + k) (n 元素數,k 數值範圍),空間複雜度 O(k)。穩定排序。
min 和最大值 max。count[min...max],記錄每個值出現次數。count[i] += count[i-1],轉換為「小於等於 i 的元素個數」,即目標位置索引 (+1)。output[count[val]-1],並 count[val]--,保證穩定性。
/**
* 計數排序
* @param {number[]} arr - 待排序整數數組 (會被修改)
* @param {number} min - 最小值 (可選,自動計算)
* @param {number} max - 最大值 (可選,自動計算)
* @returns {number[]} 排序後的數組 (原數組引用)
*/
function countingSort(arr, min, max) {
if (!arr || arr.length <= 1) return arr;
// 1. 自動計算範圍
if (min === undefined || max === undefined) {
min = max = arr[0];
for (var i = 1; i < arr.length; i++) {
if (arr[i] < min) min = arr[i];
if (arr[i] > max) max = arr[i];
}
}
var range = max - min + 1;
if (range > 1e7) {
throw new Error('數值範圍過大 (' + range + '),不適合計數排序,請改用快排/歸併排序');
}
// 2. 統計頻次
var count = new Array(range);
for (var i = 0; i < range; i++) count[i] = 0;
for (var i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
// 3. 累加計數
for (var i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 4. 反向填充輸出
var output = new Array(arr.length);
for (var i = arr.length - 1; i >= 0; i--) {
var val = arr[i];
var pos = --count[val - min]; // 先遞減再用作索引
output[pos] = val;
}
// 5. 複製回原數組 (原地排序語義)
for (var i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
return arr;
}
// 測試
var testArr = [];
for (var i = 0; i < 100; i++) {
testArr.push(Math.floor(Math.random() * 141)); // 0-140
}
console.log('排序前:', testArr.slice(0, 20));
countingSort(testArr);
console.log('排序後:', testArr.slice(0, 20));
console.log('是否有序:', testArr.every(function(v, i, a) { return i === 0 || v >= a[i-1]; }));
function countSortSimple(arr, min, max) {
var count = [], z = 0;
for (var i = min; i <= max; i++) count[i] = 0;
for (var i = 0; i < arr.length; i++) count[arr[i]]++;
for (var i = min; i <= max; i++) {
while (count[i]-- > 0) arr[z++] = i;
}
return arr;
}
| 優勢 | 劣勢/限制 |
|---|---|
| 線性時間 O(n+k),比任何比較排序快 | 僅適用於整數 (或可映射為整數的數據) |
| 穩定排序,相等元素相對順序不變 | 數值範圍 k 過大時空間/時間退化 (k > 10^7 不建議) |
| 非比較型,無比較操作開銷 | 需額外 O(k) 空間 |
| 適合作為基數排序 子程序 | 不適用於浮點數、字符串、大對象直接排序 |
const countingSortModern = (arr, min = Math.min(...arr), max = Math.max(...arr)) => {
const range = max - min + 1;
if (range > 1e7) throw new RangeError('Value range too large for counting sort');
const count = new Uint32Array(range); // 類型化數組,節省內存、速度更快
for (const v of arr) count[v - min]++;
for (let i = 1; i < range; i++) count[i] += count[i - 1];
const output = new Array(arr.length);
for (let i = arr.length - 1; i >= 0; i--) {
output[--count[arr[i] - min]] = arr[i];
}
return output; // 返回新數組,函數式風格
};