代码

#include <algorithm>
#include <queue>
using namespace std;

const int B = 1 << 16;
queue<unsigned> cnt[B];

void sort(unsigned *a, int n) {
	--a;
	for(int i = 1; i <= n; ++i)
		cnt[a[i] & ((1 << 16) - 1)].push_back(a[i]);
	for(int i = 0, p = 0; i < (1 << 16); ++i) {
		while(cnt[i].size())
			a[++p] = cnt[i].front(), cnt[i].pop();
	}
	
	for(int i = 1; i <= n; ++i)
		cnt[a[i] >> 16].push_back(a[i]);
	for(int i = 0, p = 0; i < (1 << 16); ++i) {
		while(cnt[i].size())
			a[++p] = cnt[i].front(), cnt[i].pop();
	}
}

评测结果