基数排序
需要处理的数字
24、21、123、321、122、23、32
| 类型 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 个位计数器 |
0 |
2 |
2 |
2 |
1 |
0 |
0 |
| 求前缀和(是每一个元素出现的位置) |
0 |
2 |
4 |
6 |
7 |
7 |
7 |
到这一步之后每放入一个元素之后就吧对应数字$ -1 $
#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;//计数器清0
for (int j = 0; j < n; j++) cnt[val[j] / base
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
cnt[val[j] / base
}
for (int j = 0; j < n; j++) val[i] = temp[j];/*把数组导入*/
base *= k;/*增加base，转换为进位操作，计算下一位*/
}
}
int main()
{
init();
solve();
for (int i = 0; i < n; i++) cout << val[i] << ;
cout << endl;
return 0;
cpp