代码

#include <algorithm>
//#include <cstdio>
int indx[65536];
int se[100000000];
void sort(unsigned *a, int n) {
	for (int i = 0; i < n; i++) {
		indx[a[i] & 0xffff]++;
	}
	for (int i = 1; i < 65536; i++) {
		indx[i] += indx[i - 1];
	}
	for (int i = n - 1; ~i; i--) {
		int sf = a[i] & 0xffff;
		se[--indx[sf]] = a[i];
	}
	for (int i = 0; i < n; i++) {
		a[i] = se[i];
	}
	for (int i = 0; i < 65536; i++) {
		indx[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		indx[a[i] >> 16]++;
	}
	for (int i = 1; i < 65536; i++) {
		indx[i] += indx[i - 1];
	}
	for (int i = n - 1; ~i; i--) {
		int sf = a[i] >> 16;
		se[--indx[sf]] = a[i];
	}
	for (int i = 0; i < n; i++) {
		a[i] = se[i];
	}
}
//O(\sum{Index}+\tot{Index}*n)
//int main() {
//	unsigned soe[] = {142, 362, 62, 436};
//	sort(soe, 4);
//	for (int i = 0; i < 4; i++) {
//		printf("%u ", soe[i]);
//	}
//}

评测结果