代码

#include<bits/stdc++.h>
#define REP(i,first,last) for(register int i=(first);i<=(last);++i)
#define CLEAN(a) memset(a,0,sizeof(a))
const int MAXN=1e8+5;
const int W=1e5;
unsigned b[MAXN];
int sum[W+5];
int cnt[W+5];
void sort(unsigned *a,int n)
{
	for(register int i(0);i<n;++i)
	{
		++sum[a[i]%W];
	}
	REP(i,1,W)
	{
		sum[i]+=sum[i-1];
		cnt[i]=sum[i-1];
	}
	for(register int i(0);i<n;++i)
	{
		b[cnt[a[i]%W]++]=a[i];
	}
	memcpy(a,b,sizeof(b));
	CLEAN(sum);
	for(register int i(0);i<n;++i)
	{
		++sum[a[i]/W];
	}
	cnt[0]=0;
	REP(i,1,W)
	{
		sum[i]+=sum[i-1];
		cnt[i]=sum[i-1];
	}
	for(register int i(0);i<n;++i)
	{
		b[cnt[a[i]/W]++]=a[i];
	}
	memcpy(a,b,sizeof(b));
}

评测结果