计数排序

定义

计数排序（英语：Counting sort）是一种线性时间的排序算法。

过程

计数排序的工作原理是使用一个额外的数组 cnt，其中第 $cnt[i]$ 为原序列 $A$ 中值等于 $i$ 的元素的个数，然后根据数组 cnt 来将 A 中的元素排到正确的位置。

它的工作过程分为：

• 统计每个数字的出现次数。
• 遍历值域范围，输出 cnt[i] 次 $i$ 即可。

具体说明与示例

假设待排序数组为：

A = [1, 5, 3, 3, 100, 100]

• 统计计数 初始化计数数组 cnt 大小为值域 $w+1$（本例中 $w = 100$），所有元素初始为 $0$。 遍历 A，更新：

  • cnt[1] = 1
  • cnt[3] = 2
  • cnt[5] = 1
  • cnt[100] = 2

• 输出排序结果 遍历范围 i 从 0 到 w： 对于每个 i，输出 cnt[i] 次 i。

  • 输出 1 一次 $\to$ [1]
  • 输出 3 两次 $\to$ [1, 3, 3]
  • 输出 5 一次 $\to$ [1, 3, 3, 5]
  • 输出 100 两次 $\to$ [1, 3, 3, 5, 100, 100]

最终得到有序数组。

---

具体实现

设待排序数组为 A[1..n]，值域为 [0..w]：

// 初始化计数数组，全局变量自动初始化为 0
for i = 0 to w:
    cnt[i] = 0

// 统计每个值的出现次数
for i = 1 to n:
    cnt[A[i]] = cnt[A[i]] + 1

// 输出已排序序列
for i = 0 to w:
    for j = 1 to cnt[i]:
        output(i)

伪代码

\[ \begin{array}{ll} 1 & \textbf{for } i\gets 0\textbf{ to }w\\ 2 & \qquad cnt[i]\gets 0\\ 3 & \textbf{for } i\gets 1\textbf{ to }n\\ 4 & \qquad cnt[a[i]]\gets cnt[a[i]] + 1\\ 5 & \textbf{for } i\gets 0\textbf{ to }w\\ 6 & \qquad \textbf{for } j\gets 0\textbf{ to }cnt[i]\\ 7 & \qquad\qquad print(i)\\ \end{array}\]

---

性质

• 时间复杂度
  • $O(n + w)$，其中 $n$ 为元素个数，$w$ 为值域范围。
  • 当 $w=O(n)$ 时，计数排序可达到线性时间。
• 空间复杂度
  • 需要额外 $O(w)$ 大小的计数数组。
  • 若 $w$ 过大，则空间开销和初始化时间会大幅增加。
• 稳定性
  • 计数排序是一种稳定的排序算法。
  • 通过累加计数并逆序输出（或在输出时按原序遍历输入），可保证相等元素的相对顺序不变。

待排序元素的值域 $w$ 不能太大。如果太大会造成空间超限。例如输入 $n$ 个 $0\sim 10^9$ 以内的数字进行排序，此时显然无法使用计数排序。

---