代码

unsigned B[100000005];
unsigned s[255+1];
void radix_sort_(unsigned *A,int l,int r){  //a[i]>=0, -O2
	const unsigned base = 255;
	A+=l-1;r-=l-1;l=1;
	register unsigned *a=A,*b=B;
	{
		for (int i=0;i<=base;++i)s[i]=0;
		for (int i=1;i<=r;++i)++s[a[i]&base];
		for (int i=1;i<=base;++i)s[i]+=s[i-1];
		for (int i=r;i>=1;--i)b[s[a[i]&base]--]=a[i];
		unsigned *tmp=a;a=b;b=tmp;
	}
	{
		for (int i=0;i<=base;++i)s[i]=0;
		for (int i=1;i<=r;++i)++s[a[i]>>8&base];
		for (int i=1;i<=base;++i)s[i]+=s[i-1];
		for (int i=r;i>=1;--i)b[s[a[i]>>8&base]--]=a[i];
		unsigned *tmp=a;a=b;b=tmp;
	}
	{
		for (int i=0;i<=base;++i)s[i]=0;
		for (int i=1;i<=r;++i)++s[a[i]>>16&base];
		for (int i=1;i<=base;++i)s[i]+=s[i-1];
		for (int i=r;i>=1;--i)b[s[a[i]>>16&base]--]=a[i];
		unsigned *tmp=a;a=b;b=tmp;
	}
	{
		for (int i=0;i<=base;++i)s[i]=0;
		for (int i=1;i<=r;++i)++s[a[i]>>24&base];
		for (int i=1;i<=base;++i)s[i]+=s[i-1];
		for (int i=r;i>=1;--i)b[s[a[i]>>24&base]--]=a[i];
		unsigned *tmp=a;a=b;b=tmp;
	}
	if (a!=A)for (int i=1;i<=r;++i)A[i]=a[i];
}

void sort(unsigned *a, int n){
	radix_sort_(a, 0, n-1);
}

评测结果