计数排序

2026 大纲不含计数排序（第七章排序只列到「（十）基数排序」）。本篇了解即可，不必按大纲条目的深度准备——保留它有两个理由：它是基数排序顺序实现的内核；而"计数"这个思路本身出过一道 408 大题（用的是另一个同名算法，见文末）。

不比较，直接算出每个元素该放哪

计数排序的想法是：对每个元素 $x$，只要知道"比 $x$ 小的元素有多少个"，就能直接算出它的最终下标——完全不做关键字比较，所以不受 $\mathrm{\Omega }(n{\log }_{2}n)$ 下界约束。

问题在于怎么高效地得到这个数。做法是三步：

第 1 步 计数：建 C[0..k]，扫描 A，让 C[v] = 值等于 $v$ 的元素个数。

第 2 步 前缀和：C[v] += C[v-1]，于是 C[v] 变成值 $\le v$ 的元素总个数。这一步之后有一个直接可用的含义：

值为 $v$ 的最后一个元素，它的下标就是 C[v] - 1。

第 3 步 输出：从后往前扫描 A，把 A[i] 放到 C[A[i]] - 1 处，然后 C[A[i]]--。

为什么第 3 步必须从后往前

这是全篇唯一需要想明白的地方。

前缀和给出的是"值为 $v$ 的最后一个该放哪"。所以：

• 从后往前扫：先遇到的是原序列中靠后的那个 $v$，把它放到靠后的位置，再让 C[v]-- 让出前一格给更靠前的 $v$ $\Rightarrow$ 同值元素的原有次序被保留，稳定。
• 从前往后扫：先遇到的是靠前的 $v$，却把它放到了"最后一个"的位置 $\Rightarrow$ 同值元素次序完全反转。

用 A 中三个 3（记为 $3_a,3_b,3_c$，分别在下标 2、5、7）验证：

扫描方向	放置次序	结果中三个 3 的次序
从后往前（正确）	$3_c\to B[6]$，$3_b\to B[5]$，$3_a\to B[4]$	$3_a,3_b,3_c$ ✓ 保持原序
从前往后（错误）	$3_a\to B[6]$，$3_b\to B[5]$，$3_c\to B[4]$	$3_c,3_b,3_a$ ✗ 完全反转

🔴 这正是基数排序"每趟分配必须稳定"的落地形式：基数排序在顺序存储下每趟就是一次计数排序，若这一趟从前往后扫，低位排好的成果就会被本趟反转掉。

（若改用链式实现，把元素依次追加到队尾、收集时先进先出，就天然稳定，不存在扫描方向的问题——这也是教材的链式基数排序用队列的原因。）

代码

// A: 输入数组，B: 输出数组，n: 元素个数，k: 最大值（取值范围 [0, k]）
void CountingSort(int A[], int B[], int n, int k) {
    int *C = (int *)malloc((k + 1) * sizeof(int));
    if (C == NULL) return;
    for (int i = 0; i <= k; i++)
        C[i] = 0;                    // 计数数组清零

    for (int i = 0; i < n; i++)
        C[A[i]]++;                   // 第 1 步：C[v] = 值为 v 的元素个数

    for (int i = 1; i <= k; i++)
        C[i] += C[i - 1];            // 第 2 步：C[v] = 值 <= v 的元素总个数

    for (int i = n - 1; i >= 0; i--) {   // 第 3 步：必须从后往前
        B[C[A[i]] - 1] = A[i];           // C[A[i]]-1 就是 A[i] 的最终下标
        C[A[i]]--;                       // 同值的下一个元素往前挪一格
    }
    free(C);
}

边界：n = 0 时三个循环里只有清零那一个会执行，B 不被写入，安全；k 必须不小于数组中的最大值，否则 C[A[i]] 越界——调用者必须保证取值范围的正确性，这是使用前提而不是实现缺陷。

$k\gg n$ 时它会退化

时间与空间都是 $O(n+k)$：清零 $O(k)$ + 计数 $O(n)$ + 前缀和 $O(k)$ + 输出 $O(n)$。三种情况完全一样，与初始序列无关。

但那两个 $O(k)$ 循环和大小为 $k$ 的计数数组是硬开销。取值范围一大（比如 32 位整数，$k=2^{32}$），它既不省时也不省空间。

🔴 这正是基数排序存在的理由：把大值域的关键字拆成 $d$ 位、每位值域只有 $r$，$O(k)$ 就被压成 $O(d\cdot r)$。

只适合顺序存储——要用计数值直接定位下标。

三步过程的逐步推演（想手动模拟一遍就展开）

以 A = {2, 5, 3, 0, 2, 3, 0, 3} 为例（$n=8$，$k=5$）。

第 1 步——计数：

值 $v$	0	1	2	3	4	5
C[v]	2	0	2	3	0	1

第 2 步——前缀和：

值 $v$	0	1	2	3	4	5
C[v]	2	2	4	7	7	8

含义举例：C[3] = 7 表示值 $\le 3$ 的元素共 7 个，因此最后一个 3 应放在下标 6。

第 3 步——从后往前放置：

扫描	A[i]	当前 C[A[i]]	放入	更新后
A[7]	3	7	B[6] = 3	C[3] = 6
A[6]	0	2	B[1] = 0	C[0] = 1
A[5]	3	6	B[5] = 3	C[3] = 5
A[4]	2	4	B[3] = 2	C[2] = 3
A[3]	0	1	B[0] = 0	C[0] = 0
A[2]	3	5	B[4] = 3	C[3] = 4
A[1]	5	8	B[7] = 5	C[5] = 7
A[0]	2	3	B[2] = 2	C[2] = 2

结果：B = {0, 0, 2, 2, 3, 3, 3, 5}

另一层价值：它背后的"计数数组 / 标记数组"是一种通用的空间换时间手法——当关键字取值范围有限时，用一个下标即取值的数组直接统计频次或标记存在性，可以把很多需要 $O(n\log n)$ 或 $O(n^2)$ 的问题压到 $O(n)$。这套手法在算法设计里反复出现。

教材里的「计数排序」是另一个算法

⚠️ 两本教材的习题里都有"计数排序"，但讲的都不是上面这个算法——同名不同物，而且408 大题考的是教材那一个。

教材版本的做法是：对每个记录，扫描整张表一遍，统计有多少个记录的关键字比它小；统计出的计数值 $c$ 就是它在新表中的存放位置。

	教材习题里的「计数排序」	本篇的计数排序
数什么	对每个元素，数有多少元素比它小	对每个取值，数出现了几次
怎么定位	计数值直接就是它的最终下标	对计数数组求前缀和，再倒序回填
前提	教材原题设"关键字互不相同"	关键字取值范围有限（$0\dots k$）
比较次数	$n(n-1)/2$	0 次关键字比较
时间	$\mathrm{\Theta }(n^2)$	$\mathrm{\Theta }(n+k)$

教材那个版本本质上是"用比较统计排名"，仍属比较排序，逃不掉 $\mathrm{\Omega }(n\log n)$ 的下界；本篇这个版本不做任何关键字比较，靠取值直接寻址，才能突破那个下界。基数排序内层用到的是本篇这一个。

考点速记

三条结论：

1. 第 3 步必须从后往前扫，这是稳定性的唯一来源，也是基数排序正确性的地基。
2. $O(n+k)$ 的"线性"以 $k$ 不太大为前提，$k\gg n$ 时退化——这正是基数排序要"拆位"的原因。
3. 教材习题里的"计数排序"是另一个算法（按排名计数，$\mathrm{\Theta }(n^2)$ 且要做 $n(n-1)/2$ 次比较）。

本篇不在 2026 大纲范围内，在 408 真题里也不单独成题（下方没有「真题练习」区块，这不是漏挂）。但教材版的计数排序出过一道 13 分大题，它挂在《排序算法对比》下：

• 给一段 cmpCountSort 代码，回答三问：① 对给定数组调用后输出数组的内容是什么；② $n$ 个元素时元素之间的比较次数是多少；③ 该算法是否稳定，不稳定则改写成稳定的。
  • 第 ① 问老实按代码模拟：双重循环里 if (a[i] < a[j]) count[j]++; else count[i]++;，最后 b[count[i]] = a[i]。
  • 第 ② 问答 ${\displaystyle \frac{n(n-1)}{2}}$——双重循环 $i$ 从 0 到 $n-2$、$j$ 从 $i+1$ 到 $n-1$，每对恰比一次。
  • 第 ③ 问答不稳定：两个相等元素 $a_i=a_j$（$i<j$）时走 else 分支给 count[i] 加一，于是靠前的那个反而排到后面。改法是把判断条件从 a[i] < a[j] 改成 a[i] <= a[j]，让相等时给 count[j] 加，靠后的排后面。

易错：别把教材版和前缀和版混起来。 大题给的是教材版（要比较、$\mathrm{\Theta }(n^2)$），本篇讲的是前缀和版（不比较、$\mathrm{\Theta }(n+k)$）。

易错：前缀和版的稳定性靠"从后往前"，教材版的稳定性靠"相等时给谁计数"。 两者的修改点完全不同。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）p271，第 8 章习题（6）："有一种简单的排序算法，叫做计数排序……表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 $c$，那么这个记录在新的有序表中的合适的存放位置即为 $c$。"
• 殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）p442，习题 9.25：同一思路，"为每个元素增加一个计数域 count，用于存放在已排好序的序列中该元素前面的元素数目"，并要求说明最多需要做 $n(n-1)/2$ 次排序码比较。
• 前缀和版的计数排序不在这两本教材的正文中，本篇按通行实现给出。

相关知识

基数排序（大纲内的分配类排序；每趟分配-收集在顺序存储下就是一次计数排序）｜ 排序的基本概念（下界的推导与适用边界、稳定性的定义）｜ 排序算法对比（教材版计数排序的那道大题挂在这一篇下）

相关文章

• 排序基本概念
• 直接插入排序
• 折半插入排序
• 希尔排序
• 冒泡排序
• 快速排序
• 简单选择排序
• 堆排序
• 归并排序
• 基数排序
• 外部排序
• 由中间状态反推排序算法
• 排序算法对比与性能实测