基数排序

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],ma,m,o=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ma=max(ma,a[i]);
	}
	while(ma)m++,ma/=10;
	while(m--){
		int l=0;
		vector<long long >b[1000];
		for(int i=1;i<=n;i++){
			b[(a[i]/o)%10].push_back(a[i]);
		}
		for(int i=0;i<=9;i++){
			for(int j=0;j<b[i].size();j++){
				a[++l]=b[i][j];
			}
		}
		o*=10;
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}