代码

/*
	Problem:	1001.cpp
	Time:		2020-08-11 16:02
	Author:		CraZYali
	E-Mail:		yms-chenziyang@outlook.com 
*/

#define file(FILE_NAME) freopen(FILE_NAME".in", "r", stdin), freopen(FILE_NAME".out", "w", stdout)

#include <iostream>
#include <cstdio>

const int w = 8, B = (1 << w) - 1;

const int maxn = 100000000;
int cnt[B + 1];
unsigned *pool, *str[B + 1];

void sort(unsigned *a, int n)
{
	pool = new unsigned[n];
	/*
	int times = 32 / w;
	REP(j, 0, times - 1)
	{
		REP(i, 0, n - 1) cnt[(a[i] >> (j * w)) & B]++;
		str[0] = pool;
		REP(i, 1, B) str[i] = str[i - 1] + cnt[i - 1], cnt[i - 1] = 0;
		REP(i, 0, n - 1) *(str[(a[i] >> (j * w)) & B]++) = a[i];
		std :: swap(a, pool);
	}
	*/
	int w = 0;
	{
		for (int i = 0; i < n; i++) cnt[a[i] & B]++;
		str[0] = pool;
		for (int i = 0; i < B; i++) str[i + 1] = str[i] + cnt[i], cnt[i] = 0;
		for (int i = 0; i < n; i++) *(str[a[i] & B]++) = a[i];
		std :: swap(a, pool);
	}
	w += ::w;
	{
		for (int i = 0; i < n; i++) cnt[a[i] >> w & B]++;
		str[0] = pool;
		for (int i = 0; i < B; i++) str[i + 1] = str[i] + cnt[i], cnt[i] = 0;
		for (int i = 0; i < n; i++) *(str[a[i] >> w & B]++) = a[i];
		std :: swap(a, pool);
	}
	w += ::w;
	{
		for (int i = 0; i < n; i++) cnt[a[i] >> w & B]++;
		str[0] = pool;
		for (int i = 0; i < B; i++) str[i + 1] = str[i] + cnt[i], cnt[i] = 0;
		for (int i = 0; i < n; i++) *(str[a[i] >> w & B]++) = a[i];
		std :: swap(a, pool);
	}
	w += ::w;
	{
		for (int i = 0; i < n; i++) cnt[a[i] >> w & B]++;
		str[0] = pool;
		for (int i = 0; i < B; i++) str[i + 1] = str[i] + cnt[i], cnt[i] = 0;
		for (int i = 0; i < n; i++) *(str[a[i] >> w & B]++) = a[i];
		std :: swap(a, pool);
	}
}

#ifdef CraZYali
unsigned a[maxn];
int main()
{
	file("1001");
	int n;scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%u", a + i);
	sort(a, n);
	for (int i = 0; i < n; i++) printf("%u%c", a[i], i == n - 1 ? '\n' : ' ');
	return 0;
}
#endif

评测结果