《算法導論》@讀書筆記@ 第八章 - 計數排序(包含js版代碼實作)

啥是計數排序

計數排序有點類似于窮舉的味道，我們把數字中每個數字出現的次數都記錄下來最後隻要依次在組合起來。比如下圖 9 出現了兩次 就在數組中放入兩個9

算法過程

1. 擷取數組中的最大值
2. 把他們分類整理并記錄每個數字出現的次數
3. 重新整理輸出數組

算法實作

function CountingSort(arr) {
    let len = arr.length;
    let max = Math.max.apply(null, arr);
    let temp = new Array(max + 1).fill(null);
    let result = [];
    for (let i = 0; i < len; i++) {
        temp[arr[i]] = temp[arr[i]] ? temp[arr[i]] + 1 : 1
    }
    temp.forEach((e, index) => {
        if (e != null) {
            for (let i = 0; i < e; i++) {
                result.push(index)
            }
        }
    })
    return result
}
module.exports = CountingSort