题目大意：
就排个序；
基本思路：
就学习一种新的排序，叫基数排序，然后这个其实就打破了常规的排序最快是n*logn的时间复杂度，我记得我以前读过一点，之所以这样好像是因为排序规则的选取，常规排序的排序规则应该就是直接比较两个数的大小吧（我觉得，有待考察），果然，这就是敢于打破规则的人的牛逼之处吧，太强啦；
代码如下（最下面是自己随手打的三组数据）：
#include<iostream> #include<sstream> #include<iomanip> #include<algorithm> #include<string> #include<queue> #include<vector> #include<list> #include<stack> #include<map> #include<set> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; #define rep(a,b,c) for(int a=b;a<=c;a++) #define drep(a,b,c) for(int a=b;a>=c;a--) #define mkp make_pair #define pub push_back #define pob pop_back typedef long long ll; typedef long double lb; typedef pair<int,int> pii; const int maxn = 100000+10; const int inf = 0x3f3f3f3f; const double eps = 1e-8; const int dx[8]={0,0,1,-1,1,1,-1,-1}; const int dy[8]={1,-1,0,0,1,-1,1,-1}; int arr[maxn]; int tmp[maxn]; int cnt[11]; int n; void print() { for(int i=0;i<n;i++) cout<<arr[i]<<" "; cout<<endl; } int maxbit()//用来求所有的数其中位数最多的有多少位； { int radix=10;//反正我觉得挺巧妙的，为啥不定义成1呢，是吧； int bit=1; for(int i=0;i<n;i++) { while(arr[i]>=radix) { radix*=10; bit++; } } return bit; } void radixsort() { int mbit=maxbit(); int radix=1; for(int i=1;i<=mbit;i++) { for(int j=0;j<10;j++) cnt[j]=0;//每次都要清0一次啊； for(int j=0;j<n;j++) { int t=(arr[j]/radix); cnt[t]++; } for(int j=1;j<10;j++) cnt[j]=cnt[j-1]+cnt[j];/*个人理解：这一步之前，cnt[k]存的就是第i位是k的数的个数，然后这个操作之后，cnt[k]存的可以理解为当前第i位是k的数的idex+1，你可能要问，为啥要+1，下标是从零开始的嘛；*/
for(int j=n-1;j>=0;j--)//为啥是从n-1开始到0，这点要仔细体会一下，很难讲，说个例子吧，比如说22，28，然后第二位都是2，你如果是从0到n-1，22，28就排倒了； { int t=(arr[j]/radix); tmp[cnt[t]-1]=arr[j]; cnt[t]--;//减一下； } for(int j=0;j<n;j++) arr[j]=tmp[j]; radix*=10;//别忘了； } } int main() { ios::sync_with_stdio(false); int T; cin>>T; while(T--) { cin>>n; for(int i=0;i<n;i++) cin>>arr[i]; radixsort(); print(); } return 0; } /* 3 8 2 5 3 7 2 3 6 10 9 11 2 33 34 89 90 23 333 222 11 100 232 33 334 88709 3 12 43 888 121 2323 */
