代码

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

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);
}

评测结果