代码

#include <algorithm>

const int N  = 1e8 + 100, B = 1 << 16;
int n;
int a[N], b[N];
int cnt[B], *p[B];
void sort(unsigned *a, int n) {
	for(int i = 1; i <= n; ++i)
		++cnt[a[i] & (B - 1)];
	for(int i = 0, *pp = b + 1; i < B; ++i)
		p[i] = pp, pp += cnt[i], cnt[i] = 0;
	for(int i = 1; i <= n; ++i)
		*p[a[i] & (B - 1)]++ = a[i];
	
	for(int i = 1; i <= n; ++i)
		++cnt[b[i] >> 16];
	for(int i = 0, *pp = a + 1; i < B; ++i)
		p[i] = pp, pp += cnt[i], cnt[i] = 0;
	for(int i = 1; i <= n; ++i)
		*p[b[i] >> 16]++ = b[i];
}

评测结果