分类
OI

排序算法 — O(d(r+n)) — 基数排序

写在前面


基数排序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

]]>

发表评论

电子邮件地址不会被公开。 必填项已用*标注