代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010,base=1000,maxlog=3;
int n,x[maxn],a[maxn],cnt,p=1,q=1;char c;
vector<int> buck[maxlog][base];
char qu[55];int qr;
inline void print(int &x){
    if (!x) putchar(48);
    while(x) qu[++qr]=x%10+'0',x/= 10;
    while(qr) putchar(qu[qr--]);
}
inline void gi(int &x){
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(x=0;c<='9'&&c>='0';c=getchar()) x=x*10+(c&15);
}
int main(){
    gi(n);
    for(register int i=0;i<n;i++) gi(a[i]);
    for(int i=0;i<maxlog;i++)
    {
        p*=base;cnt=0;
        for(int k=0;k<base;k++) buck[i][k].clear();
        for(register int j=0;j<n;j++) buck[i][(a[j]%p)/q].push_back(a[j]);
        for(int k=0;k<base;k++)
        {
            int s=buck[i][k].size();
            for(int m=0;m<s;m++) a[cnt++]=buck[i][k][m];
        }
        q*=base;
    }
    for(register int i=0;i<n;i++){
    	print(a[i]);
    	putchar(32);
    }
    return 0;
}

评测结果