基数排序

最近又有个奇奇怪怪的题目，数据为 \(n \le 1 \times 10^7\)，并且还要用到排序，普通的排序肯定会超时，然后就发现了一种 \(O(n)\)

介绍

基数排序(Radix Sort)是桶排序的扩展，它是将整数按位数切割成不同的数字，然后按每个数位分别比较以此来排序。

说详细点，也就是将所有数字统一为同样的长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。然后从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

下面就用表格来做个详细的解释：

既然从小到大排序，那么先排个位。

再排十位

最后再排百位

这便是最后的序列。

过程

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;
    }
}