代码

const unsigned int m=16,M=65535;
unsigned int a[10000010],b[10000010],c[10000010];
unsigned int cnt[65536],cnt2[65536],rank[10000010];

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[c[i]=a[i]>>m]; 
	for(i=1;i<=M;++i) cnt2[i]+=cnt2[i-1];
	for(i=n;i--;) rank[--cnt[b[i]]]=i;
	for(i=n;i--;) a[--cnt2[c[rank[i]]]]=b[rank[i]]+(c[rank[i]]<<m);
}

评测结果