标签：基数排序

写在前面

---

基数排序Redix Sort,是为数不多不是基于比较的排序，至今此类我们学过的，也就只有基数排序和桶排不基于比较，桶排的效率自然快,但是对内存的消耗不容小视，基数排序则在空间和时间都有这不错的表现，在大多数情况基本于归并排序速度相近，如果你会一些高端的优化的话，他甚至能够吊打桶排

基数排序

时间复杂度: O( d ( r + n ) )
空间复杂度: O( rd + n )

相信你已经根据前文知道，基数排序，不是基于比较的排序，哪们我们如何排序呢？ 我们知道桶排的思想是确定其有或没有，然后遍历 但是我们能不能简化？简化成将每一位桶排？ 当然可以，这就是基数排序 我们在每一位上进行桶排，让后进行下一位，直到最所有数高位 听起来貌似是很简单的问题，不过现在有一个重要的问题，怎么分离位？

十进制分离法

---

我们的数字是十进制，而且十进制分离位在C++中依旧很方便 代码:

#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[10][110000];
int redix[10][110000];
inline int ws(int t,int n){
    t--;
    while(t--){
        n/=10;
    }
    return n%10;
}
// ws 分离位数
bool x;// 判断最高位
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tmp=ws(1,a[i]);
        last_redix[tmp][++last_cnt[tmp]]=a[i];// 完成第一位的桶
    }
    for(int t=2;;t++){
        x=false;
        for(int i=0;i<=9;i++){
            for(int j=1;j<=last_cnt[i];j++){// 按照上一位的顺序，不然排序顺序会乱
                tmp=ws(t,last_redix[i][j]);
                if(tmp!=0) x=true;
                redix[tmp][++cnt[tmp]]=last_redix[i][j];// 桶排
                //j++;
            }
        }
        if(!x) break;
        memcpy(last_redix,redix,sizeof(redix));// 复制当前到上一次
        memcpy(last_cnt,cnt,sizeof(cnt));
        memset(cnt,0,sizeof(cnt));
    }
    for(int i=0;i<=9;i++)// 输出
        for(int j=1;j<=last_cnt[i];j++)
            printf("%d ",last_redix[i][j]);
}

二进制分割法

---

但是显然这种位数分离法比较耗时，要是我们能够快一点…… 等一下，二进制时直接位运算就可分离二进制位了啊 代码:

#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[2][1100];
int redix[2][1100];
inline int ws(int t,int n){
    t--;
    while(t--){
        n/=10;
    }
    return n%10;
}
bool x;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        //tmp=ws(1,a[i]);
        last_redix[(a[i])&1][++last_cnt[(a[i])&1]]=a[i];
    }
    for(int t=1;t<=31;t++){
        //x=false;
        for(int i=0;i<=1;i++){
            for(int j=1;j<=last_cnt[i];j++){
                //tmp=ws(t,last_redix[i][j]);
                //if(tmp!=0) x=true;
                redix[(last_redix[i][j]>>t)&1][++cnt[(last_redix[i][j]>>t)&1]]=last_redix[i][j];
                //j++;
            }
        }
        //if(!x) break;
        memcpy(last_redix,redix,sizeof(redix));
        memcpy(last_cnt,cnt,sizeof(cnt));
        memset(cnt,0,sizeof(cnt));
    }
    for(int i=0;i<=1;i++)
        for(int j=1;j<=last_cnt[i];j++)
            printf("%d ",last_redix[i][j]);
}

原理和上面一样，分离位数请参考下一篇: 位运算

End

]]>