算法精粹(algorithm-essentials)

感谢soulmachine@github提供内容
**计数排序**(Counting Sort)是一种O(n)的排序算法,其思路是开一个长度为`maxValue-minValue+1`的数组,然后

1. 分配。扫描一遍原始数组,以当前值-`minValue`作为下标,将该下标的计数器增1。
1. 收集。扫描一遍计数器数组,按顺序把值收集起来。

举个例子,`nums=[2, 1, 3, 1, 5]`, 首先扫描一遍获取最小值和最大值,`maxValue=5`, `minValue=1`,于是开一个长度为5的计数器数组`counter`,

1. 分配。统计每个元素出现的频率,得到`counter=[2, 1, 1, 0, 1]`,例如`counter[0]`表示值`0+minValue=1`出现了2次。
2. 收集。`counter[0]=2`表示`1`出现了两次,那就向原始数组写入两个1,`counter[1]=1`表示`2`出现了1次,那就向原始数组写入一个2,依次类推,最终原始数组变为`[1,1,2,3,5]`,排序好了。

计数排序本质上是一种特殊的桶排序,当桶的个数最大的时候,就是计数排序。