简介

计数排序(Counting Sort)是一种O(n)的排序算法，其思路是开一个长度为maxValue-minValue+1的数组，然后

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

举个例子，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]，排序好了。

计数排序本质上是桶排序的一种特例，即每个区间大小都为1的时候，桶排序就变成了计数排序。