计数排序

学习数据结构与算法
2021-05-17 14:29 · 阅读时长3分钟
小课

计数排序是一种非比较类的排序算法,它有一定的局限性,主要适用于元素的值在一定范围的数据,但是它的效率非常高,时间复杂度是O(N+K),K是数据的范围大小。

算法主要思路是

  1. 首先确定数据的范围,并定义计数数组。
  2. 统计计数数组中的每个元素在原数组中出现次数。
  3. 转换计数数组,将出现次数改为在排序后的数组中的位置。
  4. 根据计数数组,输出排序数组。

下面是数组[1, 4, 1, 5, 3, 3, 1, 2, 7] 的排序过程。

加载中...

计数排序代码实现如下

加载中...

计数排序比比较类排序最快(O(NlogN))的算法(快速排序、归并排序和堆排序)的效率还有高很多,但是前提是数组元素值在一定范围内,并且这个范围要比数组本身的元素的数量N要小,一旦K大于NlogN,这个优势就不存在了。

计数排序排序算法