#include <iostream>
using namespace std;
const int MAXN = 105;
int n, m, k, val[MAXN];
int temp[MAXN], cnt[MAXN];
void init() {
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> val[i];
int maximum = val[0];
for (int i = 1; i < n; i++)
if (val[i] > maximum) maximum = val[i];
m = 1;
while (maximum >= k) {
maximum /= k;
m++;
}}void solve() {
int base = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < k; j++) cnt[j] = 0;
for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;
for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];
for (int j = n - 1; j >= 0; j--) {
temp[cnt[val[j] / base % k] - 1] = val[j];
cnt[val[j] / base % k]--;
}
for (int j = 0; j < n; j++) val[j] = temp[j];
base *= k;
}}int main() {
init();
solve();
for (int i = 0; i < n; i++) cout << val[i] << ' ';
cout << endl;
return 0;}
假设输入的 n为不大于 100100 的正整数，k 为不小于 22 且不大于 100100 的正整数，vali 在 int 表示范围内，完成下面的判断题和单选题：
这是一个不稳定的排序算法。（ ）
该算法的空间复杂度仅与 n有关。（ ）
该算法的时间复杂度为 O(m(n+k))。（ ）
当输入为“5 3 98 26 91 37 46”时，程序第一次执行到第 33 行，val数组的内容依次为（ ）。
91 26 46 37 98
91 46 37 26 98
98 26 46 91 37
91 37 46 98 26
若 vali的最大值为 100，k取（ ）时算法运算次数最少。
2
3
10
不确定
当输入的 k比 vali的最大值还大时，该算法退化为（ ）算法。
选择排序
冒泡排序
计数排序
桶排序
发表评论