CSP-S 提高级 · CSP 2022 提高级第一轮 第 17 题

（2）

1  #include <iostream>
2  
3  using namespace std;
4  
5  const int MAXN = 105;
6  
7  int n, m, k, val[MAXN];
8  int temp[MAXN], cnt[MAXN];
9  
10 void init() 
11 {
12     cin >> n >> k;
13     for (int i = 0; i < n; i++) cin >> val[i];
14     int maximum = val[0];
15     for (int i = 1; i < n; i++)
16         if (val[i] > maximum) maximum = val[i];
17     m = 1;
18     while (maximum >= k) {
19         maximum /= k;
20         m++;
21     }
22 }
23 
24 void solve() 
25 {
26     int base = 1;
27     for (int i = 0; i < m; i++) {
28         for (int j = 0; j < k; j++) cnt[j] = 0;
29         for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
30         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
31         for (int j = n - 1; j >= 0; j--) {
32             temp[cnt[val[j] / base % k] - 1] = val[j];
33             cnt[val[j] / base % k]--;
34         }
35         for (i

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

这题考基数排序。拿到题先看 init 里怎么算位数 m，再看 solve 里 base 怎么变、cnt 怎么清零和前缀和，最后手动模拟第一轮按最低位%k排序，就能选出答案。

容易把基数排序当成不稳定，其实代码里从后往前遍历 temp 就是保稳定的关键；空间复杂度常误判为 O(n)，忽略了 cnt 数组占 O(k)；模拟第一轮时只按位分组忘了前缀和定位和从后往前放，顺序就会错；还有把退化情况看成桶排序，其实代码逻辑就是计数排序。

考点定位

这道题考查基数排序（Radix Sort）的实现细节，核心是按 k 进制从低位到高位逐位进行计数排序。命题人喜欢用一段完整代码让你判断性质、模拟过程、分析复杂度，甚至考察退化情形，属于对排序算法理解深度的典型测试。

知识点人话版

基数排序不是直接比大小，而是把每个数拆成 k 进制的一位一位看。比如十进制 98 在 k=3 时是 1012（1×27+0×9+1×3+2×1）。算法从最低位（个位）开始，对每一位做一次计数排序：先统计这 k 个余数各出现几次，再算前缀和（知道每个余数应该放哪儿），最后从后往前把数填进临时数组，保证相同位数的数相对顺序不变（稳定性）。做完一位，base 乘以 k，处理下一位，直到最高位。

命题视角：它爱挖什么坑

1. 稳定性判断：很多学生看到“基数排序”就默认不稳定，或者只凭名字猜，其实代码里第 31-34 行那个从后往前遍历 temp 的循环才是保稳定的铁证。命题人故意把“不稳定”放在判断题里，就是要你盯着代码细节。 2. 空间复杂度：cnt 数组大小是 k，temp 是 n，所以空间是 O(n+k)，不是 O(n)。题目常设陷阱让你选“仅与 n 有关”。 3. 时间复杂度：共 m 轮，每轮 O(n+k)，所以是 O(m(n+k))。有些同学会写 O(m·n) 或 O(n·k)，都错。 4. 模拟第一轮：这是重灾区。很多人只按位分组，忘了前缀和定位，更忘了从后往前放，结果顺序全乱。命题人给的选项里，只有严格按计数排序流程走出来的才是对的。 5. 退化情形：当 k 比最大值还大时，m=1，只做一轮计数排序，算法就退化成普通的计数排序。学生容易混淆“桶排序”和“计数排序”，代码里明显是计数排序（cnt 数组、前缀和、放回），不是桶排序。 6. 最优 k 值：k 越大，位数 m 越小，但每轮 O(n+k) 里的 k 变大，两者此消彼长，综合效率不确定。题目问“运算次数最少”，答案就是“不确定”。

思考心法：拿到题怎么推

第一步：看 init 函数。它读入 n、k 和数组，找最大值，然后不断除以 k 直到<k，数一下除了几次，这就是位数 m。记住：m 就是最高位在哪一层。 第二步：看 solve 的主循环。base 从 1 开始，每轮 base *= k，所以第 i 轮处理的是第 i 位（0 是最低位）。每轮里：

• 清零 cnt[0..k-1]
• 统计 val[j]/base % k 的频次
• 前缀和：cnt[j] += cnt[j-1]（现在 cnt[x] 表示余数≤x 的最后一个位置）
• 从后往前填 temp：temp[cnt[val[j]/base%k]-1] = val[j]，然后 cnt 减一
• 最后把 temp 拷回 val

第三步：结合题目具体问法，要么判断性质，要么手动模拟，要么分析复杂度。

逐题详解

判断题 1：这是一个不稳定的排序算法。（ ）

答案：B（错误） 理由：基数排序天生稳定，因为每轮计数排序都是稳定的。代码里第 31-34 行从后往前遍历 temp，正是保证相同位数字的数保持原相对顺序。所以“不稳定”是错的。