计数排序（ counting sort ）是一种稳定的线性时间排序算法，它是怎么做到的呢？
计数排序使用一个额外的数组 $C$ 来排序，数组第 $i$ 个元素 $C_i$ 表示待排序数组 $A$ 中值为 $i$ 的元素个数。排序时，先遍历待排序数组 $A$ ，并累加对应的 $C$ 元素；然后根据数组 $C$ 即可生成排序结果。
下面这个动画很好地演示了计数排序的基本原理，应该不难理解：
那么，辅助数组 $C$ 应该多大才合适呢？对于待排序数组 $A$ 数据范围内的每个整数， $C$ 必须提供一个一一对应的元素为它计数。因此，$C$ 的大小至少是 $A_{max}-A_{min}+1$ ，其中 $A_{max}$ 和 $A_{min}$ 分别是数组 $A$ 的最大值和最小值。
假设待排序数组 $A$ 的大小为 $n$ ，数据范围为 $r$ ，那么辅助数组 $C$ 的大小也为 $r$ ，因此空间复杂度是 $O(r)$ 。由于算法需要分别遍历这两个数组，因此时间复杂度是：$O(n+r)$ 。也就是说，算法执行时间跟输入元素个数呈线性关系，跟数据范围也呈线性关系。
对于数据范围很大的数组，计数排序需要消耗大量的时间和内存，特别是内存。因此，计数排序不适用于数据范围很大的场景。但对于数据范围较小的排序场景（比如从 0 到 100 之间），计数排序算法是一个不错的选择。
注意到，为便于演示，动画中的辅助数组 $C$ 是以 0 为起点分配的。实际上，出于内存考虑，$C$ 应该以 $A_{min}$ 为起点来分配。这样一来，$A$ 中的元素 $A_{i}$ 对应到 $C_{A_{i}-A_{min}}$ ，而不是 $C_{A_i}$ 。
下面是计数排序的示例代码，请结合注释和动画进行理解：
【小菜学算法】系列文章首发于公众号【小菜学编程】，敬请关注：
小菜学编程
