c++代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
//--------------------------------------------------------------------------------------
//桶排序
//              时复            空复            稳定性
//  最好情况    O(n + m)        0(n + m)            稳
//  平均情况    O(n + m)            
//  最坏情况    O(n + m)

void bucket_sort()
{
    int temp[N], s[N];
//只开了N个桶，而不是m个，因为这道题m太大了
//正常来说应该是s[m];
//这题范围规定成了[1, N];
//temp数组的作用是防止读写冲突
    for(int i = 0; i < n; i ++) s[q[i]]++;
    for(int i = 1; i < N; i ++) s[i] = s[i - 1] + s[i];   //求前缀和
    for(int i = n - 1; i >= 0; i --) temp[--s[q[i]]] = q[i];  //注意倒序
    for(int i = 0; i < n; i ++) q[i] = temp[i];
}
//--------------------------------------------------------------------------------------
//基数排序
//              时复            空复            稳定性
//  最好情况    O(d(n + r))     0(n + r)         稳
//  平均情况    O(d(n + r))            
//  最坏情况    O(d(n + r))
void radix_sort(int d, int r)
{
    int temp[N], s[r];
    int radix = 1;
    for(int i = 1; i <= d; i++)
    {
        memset(s, 0, sizeof s);
        for(int j = 0; j < n; j++) s[q[j] / radix % r]++;
        for(int j = 1; j < r; j++) s[j] += s[j - 1];
        for(int j = n - 1; j >= 0; j--) temp[--s[q[j] / radix % r]] = q[j];
        for(int j = 0; j < n; j++) q[j] = temp[j];
        radix *= r;
    }
}

int main()
{
    cin >> n;
    //输入
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);

    radix_sort(10, 10);
    //输出
    for(int j = 0; j < n; j ++) cout << q[j] << ' ';

    return 0;

}