【图解数据结构】 一组动画彻底理解计数排序

来自:五分钟学算法(微信号:blgczzz),作者:程序员小吴


计数排序

计数排序是一种非基于比较的排序算法,其空间复杂度和时间复杂度均为O(n+k),其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。该算法于1954年由 Harold H. Seward 提出。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

算法步骤

  1. 花O(n)的时间扫描一下整个序列 A,获取最小值 min 和最大值 max

  2. 开辟一块新的空间创建新的数组 B,长度为 ( max - min + 1)

  3. 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数

  4. 最后输出目标整数序列,具体的逻辑是遍历数组 B,输出相应元素以及对应的个数

算法演示

排序动画过程解释

  1. 首先,扫描一下整个序列

  2. 获得最小值为 2 ,最大值为 7

  3. 新建数组包含 2~7 的元素

  4. 再次扫描序列,将序列的值放置在新建数组中

  5. 扫描数字 5,数组中 index 为 3 的值为 5,次数为 1

  6. 扫描数字 3,数组中 index 为 1 的值为 3,次数为 1

  7. 扫描数字 4,数组中 index 为 2 的值为 4,次数为 1

  8. 扫描数字 7,数组中 index 为 5 的值为 7,次数为 1

  9. 扫描数字 2,数组中 index 为 0 的值为 2,次数为 1

  10. 扫描数字 4,数组中 index 为 2 的值为 4,次数为 2

  11. 扫描数字 3,数组中 index 为 1 的值为 3,次数为 2

  12. 按照这种节奏,扫描结束后,新建数组中存放了整个序列以及每个数字出现的次数

  13. 最后输出目标整数序列

  14. 输出数字 2,同时数组中 index 为 0 的值为 2 的元素次数变为 0

  15. 输出数字 3,同时数组中 index 为 1 的值为 3 的元素次数变为 1

  16. 同样的操作,整个序列就完全输出了

代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

Go代码实现

Java代码实现

Python代码实现

JavaScript代码实现

推荐↓↓↓
算法与数据结构
上一篇:看图轻松理解数据结构与算法系列(Radix树) 下一篇:【图解数据结构】 一组动画彻底理解桶排序