代码

#include<stdlib.h>
#include<string.h>

void sort(unsigned *a, int n) {
	const unsigned U = 1 << 16, All = U - 1;
	unsigned cnt[1 << 16];
	unsigned *b = (unsigned*)malloc(n << 18);
	memset(cnt, 0, 1 << 18);
	for (int i = 0; i < n; ++i) ++cnt[a[i] & All];
	for (int i = 1; i < All; ++i) cnt[i] += cnt[i - 1];
	for (int i = n - 1; ~i; --i) b[--cnt[a[i] & All]] = a[i];
	memset(cnt, 0, 1 << 18);
	for (int i = 0; i < n; ++i) ++cnt[b[i] >> 16];
	for (int i = 1; i < All; ++i) cnt[i] += cnt[i - 1];
	for (int i = n - 1; ~i; --i) a[--cnt[b[i] >> 16]] = b[i];
	free(b);
}

评测结果