代码

#include<cstdio>//基数排序
namespace io
{
	char buf[1<<21],*p1=buf,*p2=buf;
	inline char gc(){if(p1!=p2){return *p1++;} return p1==(p2=(p1=buf)+fread(buf,1,1<<21,stdin))?EOF:*p1++;}
#ifndef ONLINE_JUDGE
#define gc getchar
#endif
	template<class I>
	inline void read(I &x){x=0;I f=1;char c=gc();while(c<'0' || c>'9'){if(c=='-') f=-1;c=gc();}while(c>='0' && c<='9'){x=x*10+c-'0';c=gc();}x*=f;}
	template<class I>
	inline void write(I x){I tmp=(x>0?x:-x);if(x==0){putchar('0');return;}if(x<0) putchar('-');int cnt=0;while(tmp>0){buf[cnt++]=tmp%10+'0';tmp/=10;}while(cnt>0){putchar(buf[--cnt]);}}
}using namespace io;
void scanArray(int a[],int length){for(register int i=1;i<=length;read(a[i++]));}
void printArray(int a[],int length){for(register int i=1;i<=length;write(a[i]),++i,putchar(' '));}
int maxbit(int data[],int n)
{
	int weishu=1,p=10;
    for(register int i=1;i<=n;++i)
    {
        while(data[i]>=p)
        {
            p*=10;
            weishu++;
        }
    }
    return weishu;
}
int tmp[1000010];
void radixsort(int data[],int n)
{
    int d=maxbit(data,n);//最大位数
    int count[10],radix=1;
    for(register int i=1;i<=d;++i)
    {
    	for(int j=0;j<10;j++) count[j]=0;
    	int k;
        for(register int j=1;j<=n;++j)
        {
            k=(data[j]/radix)%10;//统计每个桶中的记录数
            count[k]++;
        }
        for(register int j=1;j<10;++j)
		{
			count[j]+=count[j-1];
		}
        for(register int j=n;j>=1;--j)
        {
            k=(data[j]/radix)%10;
            tmp[count[k]]=data[j];
            count[k]--;
        }
        for(register int j=1;j<=n;data[j]=tmp[j],++j);
        radix*=10;
    }
}
int a[1000010];
int main()
{
	int n;
	read(n);
	scanArray(a,n);
	radixsort(a,n);
	printArray(a,n);
	return 0;
}

评测结果