#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 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在 int 表示范围内,完成下面的判断题和单选题:
这是一个不稳定的排序算法。
该算法的空间复杂度仅与n有关。
当输入为“5 3 98 26 91 37 46”时,程序第一次执行到第 36 行,val[]数组的内容依次为( )。
91 26 46 37 98
91 46 37 26 98
98 26 46 91 37
91 37 46 98 26
2
3
10
不确定
选择排序
冒泡排序
计数排序
桶排序