基数排序MSD和LSD实现和比较

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

目录

一.前言

二.算法实现思路

三.算法实现

(1)LSD基数排序

(2)MSD排序

四.算法性能分析和比较


一.前言

基数排序的关键是“多关键词排序

基数排序(Radix Sort)是一种非比较的排序算法,它根据元素的各个位上的值将元素进行排序。它可以分为最低有效位优先(LSD)和最高有效位优先(MSD)两种实现方式。

二.算法实现思路

当使用基数排序时,可以选择使用LSD(最低有效位优先)或MSD(最高有效位优先)算法。下面是它们的算法流程的简要介绍:

LSD(最低有效位优先)算法流程:

  1. 确定待排序元素的最大位数,假设为d。
  2. 最低有效位(个位)开始,依次对元素进行稳定的计数排序(或桶排序),根据当前位的值将元素分配到对应的桶中。
  3. 按照计数排序的结果,重新排列元素顺序。
  4. 重复步骤2和3,直到处理完最高有效位(最高位)为止。
  5. 完成排序后,元素按照从低位到高位的顺序排列,得到有序序列。

MSD(最高有效位优先)算法流程:

  1. 确定待排序元素的最大位数,假设为d。
  2. 最高有效位(最高位)开始,依次对元素进行排序。
  3. 将元素根据当前位的值分割成多个子序列(桶),每个子序列中的元素具有相同的当前位值。可以使用计数排序、桶排序或递归调用基数排序来对每个子序列进行排序
  4. 递归对每个子序列重复步骤2和3,直到处理完最低有效位(最低位)为止。
  5. 合并所有子序列,得到有序序列。

三.算法实现

我们用java语言对两种排序进行实现

(1)LSD基数排序

从低位到高位排序,我们首先需要获得我们需要排序的位数digit
static int getNumDigits(int[] num) {//获得最大的数的位数
    int max = num[0];//最大的数
    int digits = 0;//位数
        for (int i = 0; i < num.length; i++) {
            if (num[i] > max) max = num[i];
        }
        while (max / 10 != 0) {
            digits++;
            max = max / 10;
        }
        if (max % 10 != 0) {
            digits++;
        }
        return digits;
}

获得位数后我们从低位到到高位对数字进行分组排序,其中MyQueue为队列结构的类

public static void LSD(int[] num) {
        //对数字采用最低位优先法排序
        MyQueue queue = new MyQueue(10, num.length);//分配10个队列
        int digits = getNumDigits(num);
        int mode = 1;
        while (digits != 0) {
            for (int i = 0; i < num.length; i++) {
                queue.enqueue((num[i] / mode) % 10, num[i]);
                //按桶分配,(num[i]/mode)%10表示取的位数
            }
            int k = 0;
            for (int j = 0; j < 10; j++) {
                while (!queue.isEmpty(j)) {
                    num[k] = (int) queue.dequeue(j);
                    k++;
                }
            }//出队
            digits--;//位上移
            mode = mode * 10;
        }
    }

这里对于出队部分的代码做进一步的说明

queue.dequeue(j)返回的是一个Object类型的元素,而num数组是一个int类型的数组。因此,在将元素从队列中取出后,需要进行强制类型转换(int),以将其转换为int类型,以便正确地赋值给num数组。由于Java中的泛型不支持基本数据类型,因此在取出元素时,类型会被擦除为Object

出队时一次只会返回一个元素,通过while循环保证队列中所有的元素输出完毕
(输出结果在下面)

下面补充对于长度相等的简单字符串进行LSD排序的例子,对于更加复杂的字符串排序则需要我们针对长度大小/特殊字符的比较进一步判断
public static void LSD(String[] str) {
        //对字符串采取最低位优先法
        //对数字采用最低位优先法排序
        MyQueue queue = new MyQueue(27, str.length);//分配27个队列
        //27个桶,其中第27个桶用来存储除字母以外的其他字符,不区分大小写
        int digits = str[0].length();//等长字符的长度
        int mode = 1;
        while (digits != 0) {
            for (int i = 0; i < str.length; i++) {
                int index;//桶的下标
                if (str[i].charAt(digits - 1) >= 'A' && str[i].charAt(digits - 1) <= 'Z') {
                    index = str[i].charAt(digits - 1) - 'A';
                } else if (str[i].charAt(digits - 1) >= 'a' && str[i].charAt(digits - 1) <= 'z') {
                    index = str[i].charAt(digits - 1) - 'a';
                } else {
                    index = 26;
                }//不区分大小写
                queue.enqueue(index, str[i]);
                //按桶分配
            }
            int k = 0;
            for (int j = 0; j < 27; j++) {
                while (!queue.isEmpty(j)) {
                    str[k] = (String) queue.dequeue(j);
                    k++;
                }
            }//出队
            digits--;//位上移
        }
    }

上面代码实现了从低位到高位依次进行排序的代码逻辑,详细的排序过程为:

假设有以下一组整数:[170, 45, 75, 90, 802, 24, 2, 66],我们使用LSD基数排序按照个位数、十位数和百位数进行排序。

首先,按照个位数进行排序,得到:[802, 2, 24, 45, 66, 170, 75, 90]。
然后,按照十位数进行排序,得到:[2, 24, 45, 66, 75, 90, 802, 170]。
最后,按照百位数进行排序,得到:[2, 24, 45, 66, 75, 90, 170, 802]。

通过上面的例子我们就可以清晰的看出LSD排序的具体流程

 下面是测试函数和输出结果

public static void main(String[] args) {
        int[] num = {12, 32, 2, 231, 14, 23};
        System.out.println("before sorting: " + Arrays.toString(num));
        LSD(num);
        System.out.println("after sorting: " + Arrays.toString(num));
        String[] strings = {"abc", "bde", "fad", "abd", "bef", "fdd ", "abe" };
        System.out.println("before sorting: " + Arrays.toString(strings));
        LSD(strings);
        System.out.println("after sorting: " + Arrays.toString(strings));
    }

输出结果为:

before sorting: [12, 32, 2, 231, 14, 23]
after sorting: [2, 12, 14, 23, 32, 231]
before sorting: [abc, bde, fad, abd, bef, fdd , abe]
after sorting: [abc, abd, abe, bde, bef, fad, fdd ]

(2)MSD排序

MSD算法主要采用递归和原地排序的方法,对数组进行原地排序,为了更好的展示排序的不同思路,这里的代码没有采取“新建队列”的方式来表示不同的“桶”,而是直接在数组中划分出不同的区域,来表示不同的“桶”

public class MSD {

    public static void msdSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int maxDigit = getNumDigits(arr);  // 获取最大位数
        msdSort(arr, 0, arr.length - 1, maxDigit);
    }

    private static void msdSort(int[] arr, int left, int right, int digit) {
        if (left >= right || digit <= 0) {
            return;
        }
        int[] count = new int[10];  // 计数数组,用于统计每个桶中元素的个数
        int[] temp = new int[right - left + 1];  // 临时数组,用于存储排序后的结果
        int div = (int) Math.pow(10, digit - 1);  // 用于获取当前位数上的数字

        // 统计每个桶中的元素个数
        for (int i = left; i <= right; i++) {
            int num = (arr[i] / div) % 10;
            count[num]++;
        }

        // 计算每个桶中元素在结果数组中的起始位置
        int[] startIndex = new int[10];
        int prevCount = 0;
        for (int i = 0; i < 10; i++) {
            startIndex[i] = prevCount;
            prevCount += count[i];
        }

        // 将元素按照当前位数分配到对应的桶中
        //手动分桶
        for (int i = left; i <= right; i++) {
            int num = (arr[i] / div) % 10;
            temp[startIndex[num]] = arr[i];
            startIndex[num]++;
        }


        // 将排序后的结果复制回原数组
        System.arraycopy(temp, 0, arr, left, temp.length);

        // 对每个桶中的元素递归进行排序
        for (int i = 0; i < 10; i++) {
            int bucketLeft = left + startIndex[i] - count[i];
            int bucketRight = left + startIndex[i] - 1;
            msdSort(arr, bucketLeft, bucketRight, digit - 1);
        }
    }

    static int getNumDigits(int[] num) {//略}


    public static void main(String[] args) {
        int[] arr = {802, 2, 24, 45, 66, 170, 75, 90};
        msdSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

msd和lsd,数据结构题目,java,算法,数据结构

以上是在对int类型进行排序时的代码实现, 将大小比较和Comparable类结合可以实现更多数据类型的排序

四.算法性能分析和比较

LSD  VS  MSD

1.效率:MSD基数排序在处理大量数据时具有较高的效率。它可以通过递归和分治的方式,对数据进行高效的排序。LSD直接对整个数组中的所有元素进行处理,相对而言效率比较低。

2.稳定性:LSD基数排序是一种稳定的排序算法,相同元素的相对顺序在排序后保持不变,而MSD基数排序在某些情况下可能会造成元素的相对顺序改变,因此它是一种不稳定的排序算法。

3.适用性:MSD:MSD基数排序适用于处理大范围的数据,特别是当数据具有不均匀分布的情况下。它在处理字符串排序时也很常用。LSD基数排序适用于处理数字范围较小且长度相同的数据,例如固定长度的整数。它在处理大量数字排序时具有较好的性能。

对MSD的不稳定做进一步的说明,如果全程只是用MSD算法,那么算法是稳定的,但是在任务执行过程中,对于每个子桶中的递归和排序我们可能引入更加高效的算法来提升效率,在这个过程中可能会使用一些不稳定的算法。 文章来源地址https://www.toymoban.com/news/detail-772955.html

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

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

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

相关文章

  • 【数据结构与算法】基数排序

    基数排序 基数排序(Radix Sort)属于“分配式排序”,又称“桶子法”或 bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。 基数排序法是属于稳定性的排序,基数排序法是效率高的稳定排序法。 基数排序是桶排序。 基

    2024年02月15日
    浏览(41)
  • 数据结构:排序干货!(7大排序汇总+快速排序的优化+计数排序+基数排序+桶排序)

    目录 概念 插入排序 直接插入排序 希尔排序 选择排序 直接选择排序 双向选择排序 堆排序 交换排序 冒泡排序 快速排序 Hoare法 挖坑法 前后指针法 快排的优化 三数取中法 非递归快排 归并排序 分治算法+二路归并 非递归归并 应用 排序总结 其他排序 计数排序 简单版本 复杂

    2024年02月06日
    浏览(44)
  • 数据结构与算法Python版:基数排序

    简介 :基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中

    2024年01月24日
    浏览(41)
  • Python篇——数据结构与算法(第四部分:希尔排序及其讨论、计数排序、桶排序、基数排序)

    希尔排序(shell sort)是一种分组插入排序算法 首先取一个整数d1=n/2,将元素分为d1个组,每组相邻两元素之间距离为d1,在各 组内 进行直接插入排序 取第二个整数d2=d1/2,重复上述分组排序过程,知道di=1,即所有元素在同一组内进行直接插入排序。 希尔排序每趟并不使某些

    2024年02月07日
    浏览(39)
  • 【数据结构初阶】十、快速排序(比较排序)讲解和实现(三种递归快排版本 + 非递归快排版本 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】九、排序的讲解和实现(直接插入 希尔 直接选择 堆 冒泡 -- C语言)

    2024年02月08日
    浏览(45)
  • 基数排序(桶排序)——C语言实现

      本期我们讲解基数排序,基数排序讲完后,我们的常用排序算法专栏就已经讲完了,后续可能会出一些排序优化问题,以及排序算法结合C语言实战,比如 迷宫求解 、 🅿停车场系统 、 机房预约系统 以及 植物大战僵尸外挂 等等小项目。本人 从零开始学习云计算 的专栏

    2024年02月03日
    浏览(35)
  • 基数排序--C++实现

    对于待排序的base进制的一维数组。建立base(0~base - 1)个桶。 第digit轮, 根据 val % (base (digit))将数据放入桶中,放桶时插入排序, 直到所有数据都放在了0号桶。 k 次 bucketsort ,和将桶内数据放回原数组。 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 = f l oor ( l

    2024年02月07日
    浏览(34)
  • 【数据结构初阶】九、五种比较排序的讲解和实现(直接插入 \ 希尔 \ 直接选择 \ 堆 \ 冒泡 -- C语言)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)-CSDN博客  ====

    2024年02月08日
    浏览(49)
  • 快速排序的非递归实现、归并排序的递归和非递归实现、基数排序、排序算法的时间复杂度

    我们使用一个栈来模拟函数的递归过程,这里就是在利用栈分区间。把一个区间分为 [left,keyi-1][key][keyi+1,right]递归下去,直至区间不存在或left right。 如图所示: 先把整体的区间压进去,然后出栈,处理完毕后找到keyi再分为左右两个区间。然后往栈里压有区间,压左区间,就

    2024年02月17日
    浏览(49)
  • 内部排序算法比较-数据结构C语言课设

    名称: 内部排序算法比较 内容: 在教科书中,各种内部排序算法的时间复杂的分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各种算法的比较次数和移动次数,以取得直观感受。 任务: (1)对以下7中常会用的内部排序算法进行比较

    2024年02月12日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包