Skip to main content

计数排序

算法模式：空间换时间​

思路：计数排序为桶排序一种

  1. 统计每个数出现次数及最大值
  2. 双 for 排序（包括重复）

时间复杂度： O(n+k)

let arr=[1,3,6,62,3,44,89,632];

function countSort(arr){
    // 为了排除小于空数组
    if(arr.length <= 1){return arr}

    let hash = {}
    let result = []
    let max = 0
    for(let i=0;i<arr.length;i++){
        if(!hash[arr[i]]){
            hash[arr[i]] = 1
        }else{
            hash[arr[i]] += 1
        }
        if(max < arr[i]){
            max = arr[i]
        }
    }

    for(let i=0;i<=max;i++){
        for(let j=0;j<hash[i];j++){
            result.push(i)
        }
    }

    return result
}

console.log(countSort(arr))