DIV CSS 佈局教程網

JavaScript 計數排序(Counting Sort)實作與原理解析
編輯:JavaScript綜合知識     

計數排序是一種線性時間的排序演算法。它不做任何元素之間的比較,而是靠「統計每個值出現了幾次」來決定排列結果,因此在特定條件下比所有基於比較的排序(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() 慢得多,而且會吃掉大量記憶體。

若遇到負數或浮點數,做法是「平移」與「縮放」:先減去最小值讓所有數變成非負整數,排序完再加回去。若是小數,可以乘以一個倍數轉成整數處理,但要小心精度問題。

現代 JavaScript 的對照寫法

實務上,一般的排序需求直接用原生 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);      // 依出現次數遞減
    });
}

演算法的價值在於理解「用空間換時間」這個取捨。知道計數排序的存在,遇到合適場景時能想到它,這比背下實作更重要。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved