阅读 2105

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

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

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

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

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

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

首先查一查每个元素都出现了多少次,比如元素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特别大时,将会使用很多空间。

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

希望有所帮助,本文完。



本系列已经发表文章:

关注下面的标签,发现更多相似文章
评论