最近又有个奇奇怪怪的题目，数据为 \(n \le 1 \times 10^7\)，并且还要用到排序，普通的排序肯定会超时，然后就发现了一种 \(O(n)\)
介绍
基数排序(Radix Sort)是桶排序的扩展，它是将整数按位数切割成不同的数字，然后按每个数位分别比较以此来排序。
说详细点，也就是将所有数字统一为同样的长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。然后从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
下面就用表格来做个详细的解释：
| 最开始的序列 |
|---|
| 214 |
| 135 |
| 413 |
| 435 |
| 533 |
| 345 |
| 532 |
| 421 |
| 654 |
| 431 |
既然从小到大排序，那么先排个位。
| 排完个位后 |
|---|
| 421 |
| 431 |
| 532 |
| 413 |
| 533 |
| 214 |
| 654 |
| 135 |
| 435 |
| 345 |
再排十位
| 排完十位后 |
|---|
| 413 |
| 214 |
| 421 |
| 431 |
| 532 |
| 533 |
| 135 |
| 435 |
| 345 |
| 654 |
最后再排百位
| 排完百位后 |
|---|
| 135 |
| 214 |
| 345 |
| 413 |
| 421 |
| 431 |
| 435 |
| 532 |
| 533 |
| 654 |
这便是最后的序列。
过程
1.查找数组a的最大值，并求出最大值的位数，作为循环的次数
2.统计所有数字某一位，用个桶 \(ct\) 来记个数。
3.然后做个前缀和ct[i]+=ct[i-1]，那么每个数的某一位 \(x\) 的排名就应该在 \(ct[x-1]+1 \sim ct[x]\)。
4.然后按照上一次排序的结果，利用 \(ct\) 逐一放进另一个数组，再赋值到原来数组上。
5.重复进行（2）（3）（4）的操作。
代码
int maxbit(int a[],int n){
int maxx=0;
for(int i=1;i<=n;i++){
int s=0,p=a[i];
while(p!=0){
p=p/10;
s++;
}
maxx=max(maxx,s);
}
return maxx;
}
void Radix_Sort(int a[],int n){
int m=maxbit(a,n),g=1;
for(int t=0;t<=m;t++){
for(int i=0;i<=9;i++)
ct[i]=0;
for(int i=1;i<=n;i++){
int p=(a[i]/g)%10;
ct[p]++;
}
for(int i=1;i<=9;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--){
int p=(a[i]/g)%10;
rak[ct[p]]=a[i];
ct[p]--;
}
for(int i=1;i<=n;i++){
a[i]=rak[i];
}
g=g*10;
}
}