代码

const unsigned int m=16,M=65535;
unsigned int b[10000008],rank[10000008],cnt[66666],cnt2[66666];

void sort(unsigned *a, int n)
{
	int i;
	for(i=0;i<n;++i) ++cnt[(b[i]=a[i])&M];
	for(i=1;i<=M;++i) cnt[i]+=cnt[i-1];
	for(i=0;i<n;++i) ++cnt2[b[i]>>m]; 
	for(i=1;i<=M;++i) cnt2[i]+=cnt2[i-1];
	for(i=n;i--;) rank[--cnt[b[i]&M]]=i;
	for(i=n;i--;) a[--cnt2[b[rank[i]]>>m]]=b[rank[i]];
}

评测结果