基数排序--C++实现

这篇具有很好参考价值的文章主要介绍了基数排序--C++实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 描述

对于待排序的base进制的一维数组。建立base(0~base - 1)个桶。
第digit轮, 根据 val % (base << (digit))将数据放入桶中,放桶时插入排序, 直到所有数据都放在了0号桶。

2. 代码


#include <iostream>
#include <algorithm>

struct bucket{

    explicit bucket(int val = 0,struct  bucket *next = nullptr):val_(val),next_(next)
    {}
    ~bucket()
    { }

    void insert(struct bucket *ins)
    {
        struct bucket *cur = this;

        while (cur->next_ && ins->val_ >= cur->next_->val_)
            cur = cur->next_;

        ins->next_ = cur->next_;
        cur->next_ = ins;
    }
    int nodeNum() const
    {
        int cnt = 0;
        auto cur = this;
        while (cur->next_) {
            ++cnt;
            cur = cur->next_;
        }

        return cnt;
    }


    int val_;
    struct bucket *next_;
};

int put2arr(int *arr, struct bucket *bucketArr, int base)
{
    int bucketNum = 0;
    int idx = 0;

    for ( int i = 0; i < base; ++i) {

        struct bucket *cur = &bucketArr[i];

        if ( cur && cur->next_) {
            ++bucketNum;
            cur = cur->next_;
            while (cur) {
                arr[idx++] = cur->val_;
                cur = cur->next_;
            }
        }

        bucketArr[i].next_ = nullptr;
    }

    return bucketNum;
}


void radixSort(int *arr, int len, int base)
{
    if ( !len || !arr || (base < 0 || base > 16) )
        return ;

    auto bucketArr = new bucket[base];
    auto dataArr = new bucket[len];

    int nonEmptyCnt = 0;
    int modNum = 1;

    while ( nonEmptyCnt != 1) {

        for (int i = 0;i < base;++i)
            bucketArr[i].next_ = nullptr;

        for (int i = 0; i < len; ++i) {
            int bucketIdx = arr[i] / modNum % 10;
            dataArr[i].val_ = arr[i];
            dataArr[i].next_ = nullptr;

            bucketArr[bucketIdx].insert(&dataArr[i]);
        }

        nonEmptyCnt = put2arr(arr, bucketArr, base);
        modNum *= 10;
    }


    put2arr(arr, bucketArr, base);

    for (int i = 0; i < len; ++i)
        dataArr[i].next_ = nullptr;


    delete []bucketArr;
    delete []dataArr;
}

int main()
{
    std::cout << "Hello, World!" << std::endl;

    int arr[] = { 21,9, 1234, 19, 0, 8, 20, 11};
    int len   = static_cast<int>(sizeof(arr)/sizeof(arr[0]));


    std::cout << len << std::endl;

    radixSort( arr, len, 10);


    for ( int i = 0; i < len; ++i)
        std::cout << arr[i] << "\t";

    std::cout << std::endl;

    return 0;
}

3. 理解

kbucketsort,和将桶内数据放回原数组。
k = f l o o r ( l o g b a s e ( m a x V a l ) ) ‘ k = floor(log_{base}(maxVal))` k=floor(logbase(maxVal))

4. Ref

GeekForGeek文章来源地址https://www.toymoban.com/news/detail-469110.html

到了这里,关于基数排序--C++实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 桶排序 — 计数排序和基数排序

    计数排序 int类型数组,其中存的是员工的年龄。比如说16 - 150。对于这样的数据来讲,数据状况是受限的。此时如果将数组从小到大进行排序,该如果实现? 这个实现很简单,实现一个统计数组范围从 0 ~ 150,新数组下标对应着老数组的值,新数组的值对应着老数组相同值的

    2024年02月07日
    浏览(37)
  • 25.选择排序,归并排序,基数排序

    目录 一. 选择排序 (1)简单选择排序 (2)堆排序 二. 归并排序 三. 基数排序 四. 各种排序方法的比较 (1)时间性能 (2)空间性能 (3)排序方法的稳定性能 (4)关于“排序方法的时间复杂度的下限” 一. 选择排序 (1)简单选择排序 基本思想:在待排序的数据中选出最

    2024年02月10日
    浏览(38)
  • 排序算法————基数排序(RadixSort)

    什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(K+M ) 基数排序是一种借助多的思想对单逻辑进行排序的方法。 基数排序根据每个位来分配

    2024年02月13日
    浏览(34)
  • 【手撕排序算法】---基数排序

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 我们直到一般的排序都是通过的 比较和移动 这两种操作来进行排序的。 而今天介绍的基数排序并不是依靠的 比较和移动 来

    2024年02月16日
    浏览(34)
  • 不基于比较的排序:基数排序

    本篇只是讨论桶排序的具体实现,想了解更多算法内容可以在我的博客里搜,建议大家看看这篇排序算法总结:排序算法总结_鱼跃鹰飞的博客-CSDN博客  桶排序的原理: 代码:sort1是一个比较二逼的实现方式浪费空间,sort2是一个正式的方法 

    2024年02月13日
    浏览(36)
  • 排序算法——基数排序(C语言)

    什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(K+M ) 基数排序是一种借助多的思想对单逻辑进行排序的方法。 基数排序根据每个位来分配

    2024年02月13日
    浏览(33)
  • 十大排序算法(下):计数排序,基数排序,桶排序

    有n个数,取值范围是 0~n,写出一个排序算法,要求时间复杂度和空间复杂度都是O(n)的 我们知道,前面介绍的基于比较的排序算法中,最好的算法,其平均时间复杂度都在O(N),达到线性的时间复杂度就要使用新的排序算法,而这种方法,就称为是计数排序。 计数排序的思路

    2024年02月05日
    浏览(36)
  • 深入浅出排序算法之基数排序

    目录 1. 前言 1.1 什么是基数排序⭐⭐⭐ 1.2 执行流程⭐⭐⭐⭐⭐ 2. 代码实现⭐⭐⭐ 3. 性能分析⭐⭐ 3.1 时间复杂度 3.2 空间复杂度 一个算法,只有理解算法的思路才是真正地认识该算法,不能单纯记住某个算法的实现代码! (1) 通过键值得各个位的值,将要排序的元素分配

    2024年02月08日
    浏览(54)
  • 归并交换基数简单选择排序

    基本思想就是:两两进行比较,如果发生逆序则进行交换,直到所有的记录都排好为止。 常见的交换排序方法: 冒泡排序 O ( n 2 ) O(n^2) O ( n 2 ) 快速排序 O ( n l o g 2 n ) O(nlog_2n) O ( n l o g 2 ​ n ) 冒泡排序就是基于简单的交换思想。每趟不断将记录两两比较,并按前小后大规则交

    2024年02月15日
    浏览(40)
  • 基数排序

    基数排序是一种非常快且好写的排序。 以前一直以为基数排序就是桶排,现在发现自己很智慧,警钟长鸣。 基数排序是一个以桶排为基础的排序。 桶排我就不多说了,简单且 (O(n)) 。 但是桶排有一个弊端,就是由于考试时空间限制是 (10^8) 左右,可需要排序的数据是 (

    2024年02月12日
    浏览(29)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包