我想知道这是为什么 –费曼
计数：数一数每个元素重复出现的次数
统计完后，从小到大按照统计的重复次数一个个填充到一个新数组
从查和排两个部分讲
查
记下每个元素出现的重复次数
1
2
3
4
5
6
7
|
let array = [3, 2, 1, 2, 3, 2, 0, 4]
let counts = []
for (let v of array) {
counts[v] = (counts[v] || 0) + 1
}
console.log(counts)
|
排
1
2
3
4
5
6
7
8
9
10
|
let result = []
for (let i = 0; i< counts; i++) {
let count = counts[i]
while(count>0) {
result.push(i)
count--
}
}
console.log(result)
|
优化-支持负整数排序
利用数组的key来表示元素，value来表示元素重复的次数，真是太棒了
但也有局限，key只能是0或者正整数，这就意味着待排序的数组的元素也必须是0或者正整数
在深入js的第16篇中曾提到过bias偏差值这个概念，在不方便存储负数的时候，把所有值都加上bias使得所有值都大于等于0，等要读取的时候再减去bias
这里也可以这么优化，使得计数排序可以支持负数正数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
let array = [-3, -2, -1, -2, -3, -2, 0, -4]
let counts = [], result = []
let min = Math.min(...array) // 这里min的正负不确定
for (let v of array) {
// min的正负不确定 v-min可以保证都大于0
counts(v - min) = (counts[v - min] || 0) + 1
}
for (let i = 0; i < counts.length; i++) {
let count = counts[i]
while (count > 0) {
result.push(i + min)
count--
}
}
|
这里的result是新数组，需要额外占用空间，可以继续优化
优化空间复杂度
想法是直接在原数组上替换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
let array = [-3, -2, -1, -2, -3, -2, 0, -4]
let counts = [], index = 0
let min = Math.min(...array)
for (let v of array) {
counts(v - min) = (counts[v - min] || 0) + 1
}
for (let i = 0; i < counts.length; i++) {
let count = counts[i]
while (count > 0) {
// 主要看这里
array[j] = i + min
index++
count--
}
}
|
复杂度 && 总结
计数排序适合整数排序，时间复杂度为O(n+k)。
简单说明一下为啥是O(n+k)。这里使用了两层循环，外层由counts的length——待排数组最值之差（记为k）——决定的，
而while循环次数是count决定的，而所有count之和正好为array的length（记为n）。
另外关于空间的使用，开篇实现方式的空间复杂度为O(n+k)，完整代码里的实现的空间复杂度为O(k)。
可见当k特别大时，将会使用很多空间。
我创建了一个集合jest可以测试算法的靶场项目：
https://github.com/Llane00/algorithm-range-tests
将同步文章中的代码到这个项目下
使用vscode的读者可以安装拓展插件jest，这个插件可以自动检测test文件自动运行，非常方便。
感谢老姚的文章：手写算法并记住它：计数排序
