代码

//基数排序
#include<stdio.h>
const int P=65535;
const int M=1e8+5;
int n,A[M],temp[M],pos[M],neg[M],cnt[P+5],j,k;
void Input() {
	scanf("%d",&n);
	for(int i=0; i<n; i++)scanf("%d",&A[i]);
}
void Sort() {
	for(int i=0; i<n; i++) {
		if(A[i]>=0)pos[j++]=A[i];
		else neg[k++]=-A[i];
	}
	for(int i=0; i<j; i++)cnt[pos[i]&P]++;
	for(int i=1; i<=P; i++)cnt[i]+=cnt[i-1];
	for(int i=j-1; i>=0; i--)temp[--cnt[pos[i]&P]]=pos[i];
	for(int i=0; i<=P; i++)cnt[i]=0;
	for(int i=0; i<j; i++)cnt[(temp[i]>>16)&P]++;
	for(int i=1; i<=P; i++)cnt[i]+=cnt[i-1];
	for(int i=j-1; i>=0; i--)pos[--cnt[(temp[i]>>16)&P]]=temp[i];
	for(int i=0; i<=P; i++)cnt[i]=0;
	for(int i=0; i<k; i++)cnt[neg[i]&P]++;
	for(int i=1; i<=P; i++)cnt[i]+=cnt[i-1];
	for(int i=k-1; i>=0; i--)temp[--cnt[neg[i]&P]]=neg[i];
	for(int i=0; i<=P; i++)cnt[i]=0;
	for(int i=0; i<k; i++)cnt[(temp[i]>>16)&P]++;
	for(int i=1; i<=P; i++)cnt[i]+=cnt[i-1];
	for(int i=k-1; i>=0; i--)neg[--cnt[(temp[i]>>16)&P]]=temp[i];
}
void Output() {
	for(int i=k-1; i>=0; i--)printf("%d ",-neg[i]);
	for(int i=0; i<j; i++)printf("%d ",pos[i]);
}
int main() {
	Input();
	Sort();
	Output();
	return 0;
}

评测结果