计数排序(Counting Sort)是一种O(n)的排序算法,其思路是开一个长度为maxValue-minValue+1
的数组,然后
- 分配。扫描一遍原始数组,以当前值-
minValue
作为下标,将该下标的计数器增1。 - 收集。扫描一遍计数器数组,按顺序把值收集起来。
举个例子,nums=[2, 1, 3, 1, 5]
, 首先扫描一遍获取最小值和最大值,maxValue=5
, minValue=1
,于是开一个长度为5的计数器数组counter
,
- 分配。统计每个元素出现的频率,得到
counter=[2, 1, 1, 0, 1]
,例如counter[0]
表示值0+minValue=1
出现了2次。 - 收集。
counter[0]=2
表示1
出现了两次,那就向原始数组写入两个1,counter[1]=1
表示2
出现了1次,那就向原始数组写入一个2,依次类推,最终原始数组变为[1,1,2,3,5]
,排序好了。
计数排序本质上是一种特殊的桶排序,当桶的个数最大的时候,就是计数排序。