计数排序( 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}$ 。
下面是计数排序的示例代码,请结合注释和动画进行理解:
【小菜学算法】系列文章首发于公众号【小菜学编程】,敬请关注: