代码

#define fo(i,x,y) for(int i = x;i <= y;i++)
#define fd(i,x,y) for(int i = x;i >= y;i--)
#define u32 unsigned
int cnt[260];
u32 B[200000010];
void sort(u32 *A, int n)
{
	fo(i,0,255) cnt[i] = 0;
	for(u32 *i = A;i != A + n;++i) ++cnt[*i & 255];
	fo(i,1,255) cnt[i] += cnt[i - 1];
	for(u32 *i = A + n - 1;i != A - 1;--i) B[--cnt[*i & 255]] = *i;

	fo(i,0,255) cnt[i] = 0;
	for(u32 *i = B;i != B + n;++i) ++cnt[*i >> 8 & 255];
	fo(i,1,255) cnt[i] += cnt[i - 1];
	for(u32 *i = B + n - 1;i != B - 1;--i) A[--cnt[*i >> 8 & 255]] = *i;

	fo(i,0,255) cnt[i] = 0;
	for(u32 *i = A;i != A + n;++i) ++cnt[*i >> 16 & 255];
	fo(i,1,255) cnt[i] += cnt[i - 1];
	for(u32 *i = A + n - 1;i != A - 1;--i) B[--cnt[*i >> 16 & 255]] = *i;

	fo(i,0,255) cnt[i] = 0;
	for(u32 *i = B;i != B + n;++i) ++cnt[*i >> 24 & 255];
	fo(i,1,255) cnt[i] += cnt[i - 1];
	for(u32 *i = B + n - 1;i != B - 1;--i) A[--cnt[*i >> 24 & 255]] = *i;
}

评测结果