CSP-S 2022 第一轮 第27题：当输入的k比val[i]的最大值还大时，该算法退化为

题目

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 (int j = 0; j < n; j++) val[j] = temp[j];
36         base *= k;
37     }
38 }
39
40 int main()
41 {
42     init();
43     solve();
44     for (int i = 0; i < n; i++) cout << val[i] << ;
45     cout << endl;
46     return 0;
47 }

假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i]在 int 表示范围内，完成下面的判断题和单选题：

当输入的 k 比 val[i]的最大值还大时，该算法退化为（ ）算法。

选项

• A. 选择排序
• B. 冒泡排序
• C. 计数排序
• D. 桶排序

答案

C

题解

答案是 C. 计数排序。

这段代码原本实现的是基数排序：把每个数看作一个 k 进制数，从低位到高位依次排序，每一轮使用计数排序。

当 k > max(val[i]) 时（假设元素非负）：

1. 第 18 行的 maximum >= k 不成立，所以 m = 1，只进行一轮排序。
2. 这一轮 base = 1，因此：

``cpp val[j] / base % k = val[j] % k = val[j] ``

1. 第 29 行就相当于 cnt[val[j]]++，直接统计每个数出现的次数，再通过前缀和确定位置，将元素放入有序数组。

因此，整个过程退化为一次计数排序。

注意：题面没有明确要求 val[i] 非负；若存在负数，代码可能用负数作为数组下标。此题按非负整数排序的通常前提作答。