组合题
#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]++; 30         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 表示范围内,完成下面的判断题和单选题:

第1题 判断题

这是一个不稳定的排序算法。( )

A 正确
B 错误
第2题 判断题

该算法的空间复杂度仅与 n 有关。( )

A 正确
B 错误
第3题 判断题

该算法的时间复杂度为 O(m(n + k))。( )

A 正确
B 错误
第4题 单选题

当输入为“5 3 98 26 91 37 46”时,程序第一次执行到第 36 行,val[]数组的内容依次为( )。

A

91 26 46 37 98

B

91 46 37 26 98

C

98 26 46 91 37

D

91 37 46 98 26

第5题 单选题

若 val[i]的最大值为 100,k 取( )时算法运算次数最少。

A

2

B

3

C

10

D

不确定

第6题 单选题

当输入的 k 比 val[i]的最大值还大时,该算法退化为( )算法。

A

选择排序

B

冒泡排序

C

计数排序

D

桶排序

赣ICP备20007335号-2