萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 排序算法實戰:計數排序原理與高效實現

算法簡介

計數排序 是非比較型線性排序算法,適用於已知範圍的整數排序。時間複雜度 O(n + k) (n 元素數,k 數值範圍),空間複雜度 O(k)。穩定排序。

核心思想四步走

  1. 找範圍:遍歷數組找出最小值 min 和最大值 max。
  2. 統計頻次:建立計數陣列 count[min...max],記錄每個值出現次數。
  3. 累加計數:count[i] += count[i-1],轉換為「小於等於 i 的元素個數」,即目標位置索引 (+1)。
  4. 反向填充:從原數組末尾向前遍歷,將元素放入輸出數組 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) 空間
適合作為基數排序 子程序不適用於浮點數、字符串、大對象直接排序

實際應用場景

  • 考試分數排序 (0-100/0-150/0-750 範圍固定)
  • 年齡分布統計 (0-150)
  • 顏色值排序 (0-255 RGB 通道)
  • 基數排序每一位的桶排序子程序
  • 大數據預處理:已知範圍整數去重/排序

現代 JS 優化寫法


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; // 返回新數組,函數式風格
};
copyright © 萬盛學電腦網 all rights reserved