手写算法并记住它:计数排序 手写算法题

对于经典算法，你是否也遇到这样的情形：学时觉得很清楚，可过阵子就忘了？

本系列文章就尝试解决这个问题。

研读那些排序算法，细品它们的名字，其实都很贴切。

比如计数排序，所谓“计数”，就是数一数，统计每个元素重复出现的次数。

上图演示了该算法的总体流程。分为两步：查和排。

首先查一查每个元素都出现了多少次，比如元素0出现了1一次，元素1出现了一次，元素2出现了3次等。

都统计好了，然后排序的过程就简单了，从小到大按顺序填充数组即可，出现几次就填充几次就好了。“从小到大”这个词语，就体现了排序的过程。

在我看来，计数排序是所有排序算法中最简单的，也是最符合直觉的算法。查和排，这二者都很容易实现。

查，实现如下：

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, 1, 3, 2, 1]

其中counts数组是统计结果，用其下标表示待排数组的元素。其长度为5（待排数组的最大值加1）。

排，实现如下：

let result = []
for (let i = 0; i < counts.length; i++) {
 let count = counts[i]
 while(count > 0) {
 result.push(i)
 count--
 }
}
console.log(result) // [0, 1, 2, 2, 2, 3, 3, 4]

上述代码，result是新数组，当然你也可以使用array来填充，那样就需要有一个变量来记录排到第几个位置了，可以查看文末的完整实现链接。

从算法具体过程可以看出，计数排序适合整数排序。这里有个问题，假如数值中有负数怎么办？

解决之道，也容易想到，我们先遍历一遍求出数组中的最小值，以此作为偏移量就好。

假如数据是[-3, -2, -1, -2, -3, -2, 0, -4]，其中数据中数组的最小值是-4，最大值是0。我们使用counts的第0个下标表示最小值就行了。

let array = [-3, -2, -1, -2, -3, -2, 0, -4]
let counts = [], result = []
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) {
 result.push(i + min)
 count--
 }
}
console.log(result) // [-4, -3, -3, -2, -2, -2, -1, 0]

统计时要减去偏移量，排序时要加回来的。另外，可以看出counts的长度是最大值和最小值的差值加1。

这种实现方式，也避免了另外一个问题，数据集中空间浪费情形。比如数据都介于900~1000的，那么counts的长度只需要101就够了。

至此，计数排序原理和实现已经说完了。

查看完整代码：codepen。

这里总结一下，计数排序适合整数排序，时间复杂度为O(n+k)。简单说明一下为啥是O(n+k)。这里使用了两层循环，外层由counts的length——待排数组最值之差（记为k）——决定的，而while循环次数是count决定的，而所有count之和正好为array的length（记为n）。另外关于空间的使用，开篇实现方式的空间复杂度为O(n+k)，完整代码里的实现的空间复杂度为O(k)。可见当k特别大时，将会使用很多空间。

计数排序，要做到能分分钟手写出来，是需要掌握其排序原理的。先统计出现个数，然后从小到大输出即可，一旦理解就容易写出来，不需要死记硬背的。

希望有所帮助，本文完。

作者：老姚

链接：https://juejin.im/post/5d7eec9a5188254d2f656131