计数排序

概述

计数排序（Counting Sort） 是一种非比较排序算法，假设输入的 $n$ 个元素都是 $0$ 到 $k$ 之间的整数，通过计数每个值出现的次数来确定元素位置，时间复杂度为 $\Theta (n+k)$，且是稳定的排序算法。

定义

计数排序

计数排序假设输入数组 $A[\mathrm{1..}n]$ 中每个元素是 $0$ 到 $k$ 之间的整数。

算法步骤：

1. 初始化计数数组 $C[\mathrm{0..}k]$ 为全零。
2. 遍历 $A$，统计每个值出现的次数存入 $C$。
3. 对 $C$ 做前缀和，使得 $C[j]$ 等于 $\le j$ 的元素个数。
4. 从后向前遍历 $A$，利用 $C$ 确定每个元素在输出数组 $B$ 中的位置，并将 $C$ 中对应值减 1。

时间复杂度：$\Theta (n+k)$ 空间复杂度：$\Theta (n+k)$（需要输出数组和计数数组）

核心性质

稳定性

计数排序是稳定的排序算法。从后向前遍历输入数组保证了相等元素的相对顺序不变。这一性质使得计数排序可以作为 基数排序 的子程序。

适用条件

• 输入元素必须是整数（或可以映射为整数）。
• 当 $k=O(n)$ 时，计数排序的运行时间为 $\Theta (n)$，非常高效。
• 当 $k\gg n$ 时，计数排序效率较低，不适合使用。

非比较排序

计数排序不通过元素间的比较来确定顺序，因此不受 比较排序 的 $\Omega (n\lg n)$ 下界限制。

章节扩展

第8章：基数排序

计数排序是基数排序中按位排序的子程序，基数排序利用计数排序的稳定性来实现多关键字排序。

参见

• 基数排序
• 比较排序
• 稳定排序