# 计数排序
- 时间复杂度（平均）：
O(n + k) - 时间复杂度（最坏）：
O(n + k) - 时间复杂度（最好）：
O(n + k) - 空间复杂度：
O(n + k) - 稳定
计数排序是一个优秀的整数排序的算法，但是他需要更多的额外空间来存放临时数组
# 算法
申请一个长度为待排序数组最大值+1的数组用0填充，索引表示待排序数组的值，值表示该数出现的次数
遍历待排序数组，完成这个每个数字出现次数的数组
遍历这个新数组，值表示该索引表示的数的出现次数，填充原数组
function countingSort(arr) {
if (arr.length < 2) {
return arr;
}
const counts = new Array(getMaxNumber(arr) + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
counts[arr[i]]++;
}
let arrIndex = 0;
for (let i = 0; i < counts.length; i++) {
while (counts[i]) {
arr[arrIndex++] = i;
counts[i]--;
}
}
return arr;
}
function getMaxNumber(arr) {
let max = arr[0];
let i = 1;
while (i < arr.length) {
max = Math.max(max, arr[i]);
i++;
}
return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27