代码

#include <cstring>
void sort(unsigned *a, int n) {
	const unsigned U = (1 << 16) - 1;
	unsigned cnt[1<<16];
	unsigned *b = new unsigned[n];
	memset(cnt, 0, 1 << 18);
	for (int i = 0; i < n; ++i) ++cnt[a[i]];
	for (int i = 1; i < U; ++i) cnt[i] += cnt[i - 1];
	for (int i = 0; i < n; ++i) b[--cnt[a[i]]] = a[i];
	memset(cnt, 0, 1 << 18);
	for (int i = 0; i < n; ++i) ++cnt[b[i]];
	for (int i = 1; i < U; ++i) cnt[i] += cnt[i - 1];
	for (int i = 0; i < n; ++i) a[--cnt[b[i]]] = b[i];
	delete[] b;
}

评测结果