代码

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

unsigned b[100000001];

int cnt[256];

void sort(unsigned *a, int n) {
	register unsigned i, pw = 0;
	for(i=n; i>=1+3; i-=4)
	{
		a[i]=a[i-1],a[i-1]=a[i-2],a[i-2]=a[i-3],a[i-3]=a[i-4];
	}
	while(i>=1) a[i]=a[i-1],--i;
	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;
	//for(int i=1; i<=n; ++i) a[i-1]=a[i];
	for(i=1; i<=n-3; i+=4)
	{
		a[i-1]=a[i],a[i]=a[i+1],a[i+1]=a[i+2],a[i+2]=a[i+3];
	}
	while(i<=n) a[i-1]=a[i],++i;
}

评测结果