CSP-J 入门级 · CSP 2019 入门级第一轮 第 20 题

2.（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 $n$ 对 $10000$ 以内的整数，从小到大排序。

例如有三对整数 $(3,4)$、$(2,4)$、$(3,3)$，那么排序之后应该是 $(2,4)$、$(3,3)$、$(3,4)$ 。

输入第一行为 $n$，接下来 $n$ 行，第 $i$ 行有两个数 $a[i]$ 和 $b[i]$，分别表示第 $i$ 对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围 $1<n<10^7$，$1<a[i],b[i]<10^4$。

提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[] 存储第二关键字排序的结果，数组 res[] 存储双关键字排序的结果。

试补全程序。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;

int n;
unsigned a[maxn], b[maxn],res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) 
        scanf("%d%d", &a[i], &b[i]);
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < n; ++i)
        ①; // 利用 cnt 数组统计数量
    for (int i = 0; i < maxs; ++i) 
        cnt[i + 1] += cnt[i];
    for (int i = 0; i < n; ++i)
        ②; // 记录初步排序结果
    memset(cnt, 0, sizeof(cnt

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这道题考双关键字计数排序。拿到题先想：双关键字怎么排？稳定排序，先排次要关键字（b），再排主要关键字（a）。代码里 ord 存的是原数组下标，所以第一遍计数排序后，ord 里就是按 b 排好序的下标；第二遍再用 ord 里的顺序去填 res，就能保证相同 a 时 b 依然有序。

最容易错的是把第一关键字和第二关键字搞反，比如先对 a 计数排序，那样最后输出时 b 的顺序就乱了。还有很多人不理解 ord 存的是下标而不是值，导致第二遍排序时直接写 ord[--cnt[a[i]]] = a[i]，这样 ord 就被覆盖了，完全没法用。另外计数排序填位置时忘了用--cnt 从后往前填，或者遍历 ord 时顺序写反，都会破坏稳定性。

这道题考查双关键字计数排序，属于计数排序与桶排序的进阶应用，在 CSP 入门级考过 1 次，整体相关考点（一维数组）在题库中非常高频，尤其是 2023-2026 年爆发式增长，说明这类基础算法正成为近年必考项。

先理清概念：计数排序适合值域小的整数，用 cnt 数组做桶。双关键字排序要求先排次要关键字（本题是 b），再排主要关键字（a），且必须稳定——即相同 a 时，原顺序（也就是 b 的顺序）不能乱。实现稳定性的关键是：第一遍排序后，ord 数组里存的是原数组的下标，按 b 从小到大排列；第二遍排序时，遍历 ord 中的下标，依次把对应元素放到 res 中。

接下来逐空推演。第一遍对 b 计数：①处显然要统计 b[i] 出现次数，所以填 ++cnt[b[i]]（B）。然后做前缀和，cnt[i+1]+=cnt[i]，此时 cnt[x] 表示 b 值为 x 的元素应该放置的起始位置（从后往前填）。②处要把当前元素放到正确位置，因为 ord 存的是下标，所以 ord[--cnt[b[i]]] = i，选 D。注意这里必须用--cnt 从后往前填，才能保证稳定性。

第二遍对 a 计数：清空 cnt 后，③处统计 a[i] 出现次数，填 ++cnt[a[i]]（C）。同样做前缀和。④处要遍历 ord 中的下标（因为 ord 已经按 b 排好序了），对每个 ord[i]，它对应的 a 值是 a[ord[i]]，所以先统计这个 a 值，填 res[--cnt[a[ord[i]]]] = ord[i]，选 A。这里一定要用 ord[i] 而不是 i，否则就失去了第一遍排序的成果。

最后输出：res 里存的是排好序后的下标，所以直接输出 a[res[i]] 和 b[res[i]]（B）。

避坑提醒：千万别把第一遍和第二遍的计数对象搞混，也别在第二遍直接写 ord[--cnt[a[i]]] = a[i]，那样 ord 就被污染了。还有，计数排序填位置必须从后往前，用--cnt，否则相同值的元素顺序会乱。

考频与趋势：一维数组相关题目在 2023 年突然激增到 27 题，2024 年 48 题，2025 年 55 题，2026 年 59 题，可见这类基础数据结构与算法题正在成为高频考点。计数排序本身只考了 3 题（2019、2022），但结合双关键字、稳定排序等变体，未来很可能在 CSP 入门/提高级或 GESP 八级以上再次出现，尤其是涉及多关键字排序的场景。暂无足够依据预测具体年份，但建议重点掌握稳定排序的实现细节。