代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;


typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;

const int N  = 1e5 + 100, B = 1 << 16;

int n;
int a[N];
vector<int> cnt[B];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	
	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) {
		for(int j = 0; j < cnt[i].size(); ++j)
			a[++p] = cnt[i][j];
		cnt[i].clear();
	}
	
	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) {
		for(int j = 0; j < cnt[i].size(); ++j)
			a[++p] = cnt[i][j];
		cnt[i].clear();
	}
	
	for(int i = 1; i <= n; ++i)
		printf("%d%c", a[i], i == n ? '\0' : ' ');
	
	return 0;
}

评测结果