五分钟学会一个有意思的排序：计数排序

[CoderOnePolo]

由于 LeetCode 上的算法题很多涉及到一些基础的数据结构，为了更好的理解后续更新的一些复杂题目的动画，推出一个新系列 -----《图解数据结构》，主要使用动画来描述常见的数据结构和算法。本系列包括十大排序、堆、队列、树、并查集、图等等大概几十篇。

你可以在公众号 五分钟学算法 获取更多排序内容

计数排序

计数排序是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为 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 代码实现

如果你是 iOS 开发者，可以在 GitHub 上 https://github.com/MisterBooo/Play-With-Sort-OC 获取更直观可调试运行的源码。

你可以在公众号 五分钟学算法 获取更多排序内容

[stevenbipt]

计数排序伪代码：
//A:需要排序的数组
//B：排好序数组
//C[0...K]临时存储空间
counting-sort(A,B,k)
let C[0...k] be a new array
for i=0 to k
C[i]=0
for j=1 to A.length
C[A[j]]=C[A[j]]+1
for i-=1 to k
C[i]=C[i]+C[i-1]
for j=A.length downto 1
B[C[A[j]]]=A[j]
C[A[j]]=C[A[j]]-1
'''
当初被这“[]”弄得头都大了，不过慢慢调试出来发现其实挺简单的，桶排序和这个区别好像在于桶是一个区间而不是一个数，在桶里面的元素需要进一步排序，通常会使用相对较快的比较排序方法对每个桶里面的元素进行排序，当输入数据满足：所有桶的大小的平方和与总的元素数呈线性关系。桶排序的期望运行时间还是 O(n)

[wysnylc]

说得好,我选择桶排序

[ejq]

我一般管它叫统（计）排（序）

反正跟桶排差不多，这样叫也没啥问题（

[CoderOnePolo]

@wysnylc 酒桶么🤔

[CoderOnePolo]

@stevenbipt 大佬

[CoderOnePolo]

@ejq 那基数排序岂不是叫鸡排🐶

[xml123]

重力排序了解一下，sqrt(n)的复杂度

[CoderOnePolo]

@xml123 可否详情解释一下🙏，最近在收集睡眠排序、猴子排序等逗比排序的时间复杂度，打算写一写这些。

[xml123]

wiki 上叫珠排序
zh.wikipedia.org/wiki/珠排序
直接看那两张图就懂了

[Tony042]

如果是浮点数 这个算法是不是就没法用了？

[qiayue]

楼主可以透露一下这个公众号粉丝到了哪个量级吗？
千、万、十万？

[CoderOnePolo]

@Tony042 是的，题目要求整数才行

[XiaoxiaoPu]

@Tony042 浮点数用基数排序，不过需要研究下 IEEE 754，特殊处理下