跳到主要内容

简介

计数排序(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],排序好了。

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