排序算法-计数排序

原理解析

原理上来说计数排序采用的是空间换取事件的方法。
步骤：

1. 创建一个哈希表用于记录数据。
2. 遍历数组，把数组中的数字记录到哈希表中，出现第一次记为{ n:1},出现i次记录为{ n:i}。
3. 记录最大数字max。
4. 从0到max，从小到大，数字j与哈希表中一一比对，如果发现表中存在j，打印i个j。
   代码如下：

let array = [2,1,5,3,8,4,9,5]

let sort = arr =>{
let hashTable = {}, max = 0, result = []
for(let i=0; i<arr.length; i++){
if(!(arr[i] in hashTable)){
hashTable[arr[i]] = 1
  }else{
hashTable[arr[i]] += 1
 }
if(arr[i] > max) {max = arr[i]}
}
for(let j=0; j<=max; j++){
if(j in hashTable){
for(let i = 0; i<hashTable[j]; i++){
result.push(j)
    }
  }
 }
return result
}

复杂度分析

时间复杂度为 Ο(n+max)

缺点
计数排序只能用在取值范围不大的场景，而且只能为非负整数排序