计数排序

计数排序

计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为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，输出相应元素以及对应的个数

算法演示

image

排序动画过程解释

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. 同样的操作，整个序列就完全输出了

代码实现

image.png

作者：五分钟学算法
链接：https://www.jianshu.com/p/315000771cea
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。