代码

#include <algorithm>
#include <cstring>

void sort(unsigned *a, int n) {
	int cnt[256];
	unsigned b[100000001];

	register unsigned i, pw = 0;
	for (i = 0; i < n - 3; i += 4)
		++cnt[(a[i] >> pw) & 255], ++cnt[(a[i + 1] >> pw) & 255], ++cnt[(a[i + 2] >> pw) & 255], ++cnt[(a[i + 3] >> pw) & 255];
	while (i < n)
		++cnt[(a[i++] >> pw) & 255];
	for (i = 1; i < 256 - 3; i += 4)
		cnt[i + 3] += cnt[i + 2] += cnt[i + 1] += cnt[i] += cnt[i - 1];
	while (i < 256)
		cnt[i] += cnt[i - 1], ++i;
	for (i = n-1; i >= 3; i -= 4)
		b[cnt[(a[i] >> pw) & 255]--] = a[i], b[cnt[(a[i - 1] >> pw) & 255]--] = a[i - 1],
		b[cnt[(a[i - 2] >> pw) & 255]--] = a[i - 2], b[cnt[(a[i - 3] >> pw) & 255]--] = a[i - 3];
	while (i >= 0)
		b[cnt[(a[i] >> pw) & 255]--] = a[i], --i;
	pw += 8;
	memset(cnt, 0, sizeof(cnt));
	for (i = 0; i < n - 3; i += 4)
		++cnt[(b[i] >> pw) & 255], ++cnt[(b[i + 1] >> pw) & 255], ++cnt[(b[i + 2] >> pw) & 255], ++cnt[(b[i + 3] >> pw) & 255];
	while (i < n)
		++cnt[(b[i++] >> pw) & 255];
	for (i = 1; i < 256 - 3; i += 4)
		cnt[i + 3] += cnt[i + 2] += cnt[i + 1] += cnt[i] += cnt[i - 1];
	while (i < 256)
		cnt[i] += cnt[i - 1], ++i;
	for (i = n-1; i >= 3; i -= 4)
		a[cnt[(b[i] >> pw) & 255]--] = b[i], a[cnt[(b[i - 1] >> pw) & 255]--] = b[i - 1],
		a[cnt[(b[i - 2] >> pw) & 255]--] = b[i - 2], a[cnt[(b[i - 3] >> pw) & 255]--] = b[i - 3];
	while (i >= 0)
		a[cnt[(b[i] >> pw) & 255]--] = b[i], --i;
	pw += 8;
	memset(cnt, 0, sizeof(cnt));
	for (i = 0; i < n - 3; i += 4)
		++cnt[(a[i] >> pw) & 255], ++cnt[(a[i + 1] >> pw) & 255], ++cnt[(a[i + 2] >> pw) & 255], ++cnt[(a[i + 3] >> pw) & 255];
	while (i < n)
		++cnt[(a[i++] >> pw) & 255];
	for (i = 1; i < 256 - 3; i += 4)
		cnt[i + 3] += cnt[i + 2] += cnt[i + 1] += cnt[i] += cnt[i - 1];
	while (i < 256)
		cnt[i] += cnt[i - 1], ++i;
	for (i = n-1; i >= 3; i -= 4)
		b[cnt[(a[i] >> pw) & 255]--] = a[i], b[cnt[(a[i - 1] >> pw) & 255]--] = a[i - 1],
		b[cnt[(a[i - 2] >> pw) & 255]--] = a[i - 2], b[cnt[(a[i - 3] >> pw) & 255]--] = a[i - 3];
	while (i >= 0)
		b[cnt[(a[i] >> pw) & 255]--] = a[i], --i;
	pw += 8;
	memset(cnt, 0, sizeof(cnt));
	for (i = 0; i < n - 3; i += 4)
		++cnt[(b[i] >> pw) & 255], ++cnt[(b[i + 1] >> pw) & 255], ++cnt[(b[i + 2] >> pw) & 255], ++cnt[(b[i + 3] >> pw) & 255];
	while (i < n)
		++cnt[(b[i++] >> pw) & 255];
	for (i = 1; i < 256 - 3; i += 4)
		cnt[i + 3] += cnt[i + 2] += cnt[i + 1] += cnt[i] += cnt[i - 1];
	while (i < 256)
		cnt[i] += cnt[i - 1], ++i;
	for (i = n-1; i >= 3; i -= 4)
		a[cnt[(b[i] >> pw) & 255]--] = b[i], a[cnt[(b[i - 1] >> pw) & 255]--] = b[i - 1],
		a[cnt[(b[i - 2] >> pw) & 255]--] = b[i - 2], a[cnt[(b[i - 3] >> pw) & 255]--] = b[i - 3];
	while (i >= 0)
		a[cnt[(b[i] >> pw) & 255]--] = b[i], --i;
}

评测结果