代码

#include<bits/stdc++.h>
using namespace std;

unsigned b[100000001];

void sort(unsigned *a, int n) {
	int cnt[256];
	memset(cnt,0,sizeof(cnt));
	memcpy(a+1,a,n*4+4);
	register unsigned i, pw = 0;
	for (i = 1; 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; i >= 1 + 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 >= 1)
		b[cnt[(a[i] >> pw) & 255]--] = a[i], --i;
	pw += 8;
	memset(cnt, 0, sizeof(cnt));
	for (i = 1; 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; i >= 1 + 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 >= 1)
		a[cnt[(b[i] >> pw) & 255]--] = b[i], --i;
	pw += 8;
	memset(cnt, 0, sizeof(cnt));
	for (i = 1; 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; i >= 1 + 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 >= 1)
		b[cnt[(a[i] >> pw) & 255]--] = a[i], --i;
	pw += 8;
	memset(cnt, 0, sizeof(cnt));
	for (i = 1; 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; i >= 1 + 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 >= 1)
		a[cnt[(b[i] >> pw) & 255]--] = b[i], --i;
	memcpy(a,a+1,n*4+4);
}

评测结果