原理解析
原理上來說計數(shù)排序采用的是空間換取事件的方法腿准。
步驟：
- 創(chuàng)建一個哈希表用于記錄數(shù)據(jù)夭问。
- 遍歷數(shù)組倡蝙，把數(shù)組中的數(shù)字記錄到哈希表中予颤，出現(xiàn)第一次記為{ n:1},出現(xiàn)i次記錄為{ n:i}旅敷。
- 記錄最大數(shù)字max生棍。
- 從0到max，從小到大媳谁，數(shù)字j與哈希表中一一比對涂滴，如果發(fā)現(xiàn)表中存在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)
缺點
計數(shù)排序只能用在取值范圍不大的場景柔纵，而且只能為非負整數(shù)排序
