JS-排序演算法之計數和基數排序

目錄

• JS-排序演算法之計數和基數排序
  • 計數排序
  • 基數排序

計數排序

利用數組的index是天然有序的特征來排序. 例如: 已知一個亂序數組的範圍是0~10,長度未知, 我們只需要遍歷一遍數組,點出每個值出現的次數,並用一個新數組來存儲這個次數,就能做到排序. 假如數字1出現3次, 那麼新數組newAry[1]=3, 在新數組遍歷的時候輸出3次"1"

• 時間複雜度O(n~K)
• 穩定的排序演算法
• 性能: 由於是非比較排序, 速度快於其他任何排序演算法,
• 缺點: 需要知道數組值的範圍, 且不適用於範圍波動很大但長度小的數組
  • 例如: 數組長度10, 但是值的範圍在 0~1000000, 計數排序用來計數的數組將會很大
• 特點: 先遍曆數組計算數值出現次數, 然後就排序好了...

    function countSort(ary) {
        let newAry = new Array(ary.length).fill(0);
        for (const value of ary) {
            newAry[value]++;
        }
        ary = [];
        // 給ary重新賦值
        for(var i =0; i<newAry.length; i++) {
            // 迴圈數字次數
            for(var k = newAry[i]; k>0; k--) {
                ary.push(i);
            }
        }
        newAry = null;
        return ary;
    }

效果演示:

基數排序

從左到右按位排序, 先排個位, 再排十位,百位... 需要用到計數排序的方法-使用數組計數

    function radixSort(ary) {
    // 獲取最大值
    let maxNum = Math.max.apply(Math, ary);
    let t = 1,
        bucketAry = new Array(10), // 0~9的數組,用來計算數字出現次數
        temp = new Array(ary.length); // 交換數組, 用來臨時存儲排序的數
    // 這一步是計算最大數有多少位,這個位數就是要迴圈的次數
    while ((maxNum /= 10) >= 1) {
        t++;
    }
    let rate = 1,
        K= null;
    for (let i = 1; i <= t; i++) {
        // 計數數組歸零
        bucketAry.fill(0);
        // 清點數字次數
        ary.forEach((item) => {
            // 求數字最後一位的值
            k = Math.floor(item / rate) % 10;
            bucketAry[k]++;
        });
        // 通過數字次數得到該數字應該在數組中的位置
        bucketAry.reduce((total, item, index) => {
            bucketAry[index] = total + item;
            return total + item
        });
        // 通過計算的順序將ary中數存入temp數組中
        for (let j = ary.length - 1; j >= 0; j--) {
            k = Math.floor(ary[j] / rate) % 10;
            temp[bucketAry[k] - 1] = ary[j];
            bucketAry[k]--;
        }
        // 將temp相同位置的值負值給ary, 不能直接 ary = temp
        ary = ary.map((item, index)=>temp[index]);
        rate *= 10;
    }
    temp = null;
    bucketAry = null;
    return ary;
}

效果演示: