基数排序

2021-01-22 22:15

阅读：424

标签：http str int dig 相同 curd out for tmp

基数排序（radix sort）：

对个位数先排序，再对十位数排序，以此类推。。

如果数据不满足位数相同，要对不够位数的数字前面补0（或者做类似处理）。

时间复杂度O(nk)其中n为数字个数，k为最多的数字位数。

void RadixSort(vectorint>& nums){
    int maxDigits=1;
    for(const int& num:nums){   //找到最长数字位数
        maxDigits=max(maxDigits,int(to_string(num).size()));
    }
    int tmp[11][100]={0};   //临时桶，分别对应0~9数字
    int radix=1,curDigit=0;    //从倒数第一位（个位）开始
    while(curDigitmaxDigits){
        int cnt[11]={0};    //cnt[i]=k：当前轮次第i个桶已经放了k个数字
        for(const int& num:nums){
            if(num>=radix){
                int n=(num/radix)%10;    //考察数字为n
                tmp[n][cnt[n]]=num; //放入n对应的桶
                cnt[n]++;   //n对应的桶增加一个元素
            }
            else{   //当前要考察的位是0
                tmp[10][cnt[10]]=num;
                cnt[10]++;
            }
        }
        //按顺序放回原数组，其中先放回当前考察位为0的
        int index=0;
        for(int i=0;i10];++i){
            nums[index++]=tmp[10][i];
        }
        for(int i=0;i10;++i){
            for(int j=0;jj){
                nums[index++]=tmp[i][j];
            }
        }
        curDigit++; //下次循环继续考察靠前的一位
        radix*=10;  //基数*10
    }
    for(const int& num:nums){
        cout" ";
    }
}

运行结果：

技术图片

基数排序

标签：http str int dig 相同 curd out for tmp

原文地址：https://www.cnblogs.com/FdWzy/p/12886064.html

上一篇：python qml 样式（style）与主题(theme)

下一篇：java冒泡排序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：基数排序
文章链接：http://soscw.com/index.php/essay/45622.html

亲，登录后才可以留言！

基数排序

评论

热门文章

推荐文章

最新文章

置顶文章