基数排序详解(LSD方法+MSD方法+思路+图解+代码)

文章目录

  • 基数排序
    • 一、基数排序
      • 概念
      • 1.LSD排序法(最低位优先法)
      • 2.MSD排序法(最高位优先法)


基数排序


一、基数排序

概念

  • 基数排序是一种非比较型整数排序算法

  • 将整数按位数切割成不同的数字,然后按每个位数分别比较

  • 使用场景:按位分割进行排序,适用于大数据范围排序,打破了计数排序的限制

  • 稳定性:稳定

  • 按位分割技巧:arr[i] / digit % 10,其中digit为10^n。

在这里插入图片描述

1.LSD排序法(最低位优先法)

  • 从最低位向最高位依次按位进行计数排序。

  • 进出的次数和最大值的位数有关

  • 桶可以用队列来表示

  • 数组的每个元素都是队列

在这里插入图片描述

  • 1.先遍历找到最大值
  • 2.求出最高位

在这里插入图片描述

    public static void radixSortR(int[] array) {
        //10进制数,有10个桶,每个桶最多存array.length个数
        int[][] bucket = new int[10][array.length];
        //桶里面要存的具体数值

        int[] bucketElementCounts = new int[10];
        //用来计算,统计每个桶所存的元素的个数,每个桶对应一个元素

        //1.求出最大数
        int MAX = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > MAX) {
                MAX = array[i];
            }
        }
        //求最大值的位数,先变成字符串,求字符串长度
        int MAXCount = (MAX + "").length();
        //最大位数的个数,进行几次计数排序
        for (int i = 0; i < MAXCount; i++) {//i代表第几次排序
            //放进桶中
            for (int k = 0; k < array.length; k++) {
                //k相当于遍历待排数值
                //array[k] /(int) Math.pow(10, i)%10 求出每次要比较位的数
                //求的是个位,并且是对应趟数的个位
                int value = (array[k] / (int) Math.pow(10, i)) % 10;
                //根据求出的位数,找到对应桶,放到对应桶的位置
                bucket[value][bucketElementCounts[value]] = array[k];
                //不管value 为多少,bucketElementCounts[value]的值都为0
                //相当于存到对应桶的0位bucket[value][0]
                bucketElementCounts[value]++; //从0->1
                //对应桶的技术数组开始计数
            }

            //取出每个桶中的元素,赋值给数组
            int index = 0;//array新的下标
            for (int k = 0; k < bucketElementCounts.length; k++) {//遍历每个桶
                if (bucketElementCounts[k] != 0) {//桶里有元素
                    for (int j = 0; j < bucketElementCounts[k]; j++) {//比那里每个桶的元素
                        array[index] = bucket[k][j];
                        index++;
                    }
                }
                bucketElementCounts[k] =0;//每个桶遍历完后,清空每个桶的元素;
            }
        }
    }

2.MSD排序法(最高位优先法)

在这里插入图片描述

  • 从最高位向最低位依次按位进行排序。
  • 按位递归分组收集
  • 1.查询最大值,获取最高位的基数
  • 2.按位分组,存入桶中
  • 3.组内元素数量>1,下一位递归分组
  • 4.组内元素数量=1.收集元素
   /**
     * 基数排序--MSD--递归
     * @param array
     */

    public static void radixSortMSD(int[] array) {
        //1.求出最大数
        int MAX = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > MAX) {
                MAX = array[i];
            }
        }
        //求最大值的位数,先变成字符串,求字符串长度
        int MAXCount = (MAX + "").length();
        // 计算最大值的基数
        int radix = new Double(Math.pow(10, MAXCount - 1)).intValue();

        int[] arr = msdSort(array, radix);
        System.out.println(Arrays.toString(arr));
    }
    public static int[] msdSort(int[] arr, int radix){
        // 递归分组到个位,退出
        if (radix <= 0) {
            return arr;
        }
        // 分组计数器
        int[] groupCounter = new int[10];

        // 分组桶
        int[][] groupBucket = new int[10][arr.length];

        for (int i = 0; i < arr.length; i++) {
            // 找分组桶位置
            int position = arr[i] / radix % 10;
            // 将元素存入分组
            groupBucket[position][groupCounter[position]] = arr[i];
            // 当前分组计数加1
            groupCounter[position]++;
        }

        int index = 0;
        int[] sortArr = new int[arr.length];


        // 遍历分组计数器
        for (int i = 0; i < groupCounter.length; i++) {
            // 组内元素数量>1,递归分组
            if (groupCounter[i] > 1) {
                int[] copyArr = Arrays.copyOf(groupBucket[i], groupCounter[i]);
                // 递归分组
                int[] tmp = msdSort(copyArr, radix / 10);
                // 收集递归分组后的元素
                for (int j = 0; j < tmp.length; j++) {
                    sortArr[index++] = tmp[j];
                }
            } else if (groupCounter[i] == 1) {
                // 收集组内元素数量=1的元素
                sortArr[index++] = groupBucket[i][0];
            }
        }
        return sortArr;
    }

点击移步博客主页,欢迎光临~

偷cyk的图

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/172814.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

函数有返回类型,但函数体未返回类型,程序崩溃问题记录

问题 使用类指针调用函数时&#xff0c;程序崩溃。 问题定位&#xff1a; name new nameSetting;name->setName("helloworld");qDebug().noquote() << name->getName();原因 class nameSetting { public:nameSetting();QString setName(const QStri…

短视频配音软件有哪些?这些常用的短视频配音软件

短视频行业近年来发展得很快&#xff0c;几乎闯入了我们每个现代人的生活&#xff0c;它以其独有的特点和乐趣&#xff0c;也收获了大批短视频爱好者&#xff0c;配音是短视频创作过程中不可或缺的环节&#xff0c;今天&#xff0c;我们就来聊聊短视频配音及好用的配音软件。 短…

关闭bitlocker加密

windows11的笔记本电脑买回来发现分驱都处于bitlocker状态&#xff0c;上网上搜索都是说进入控制面板的安全项进行关闭&#xff0c;包括去搜索栏搜索“管理 BitLocker”&#xff0c;对搜索出来的项打开&#xff0c;经过试验&#xff0c;它们进入的是同一个位置&#xff0c;只有…

详解Python安装requests库的实例代码

文章目录 前言基本用法基本的get请求带参数的GET请求解析json关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战案例③Python小游戏源码五、面试资料六、Python兼职渠道 前…

【20年扬大真题】编写对数组求逆的递归算法

【20年扬大真题】 编写对数组求逆的递归算法 void swap(int* a, int* b) {int tmp *b;*b *a;*a tmp; } void Ni(int arr[],int left,int right) {if (left > right) {return;}swap(&arr[left], &arr[right]);Ni(arr, left 1, right - 1); } int main() {int ar…

全网最全jmeter接口测试/接口自动化测试看这篇文章就够了:跨线程组传递jmeter变量及cookie的处理

setUp线程组 setUp thread group&#xff1a; 一种特殊类型的线程组&#xff0c;用于在执行常规线程组之前执行一些必要的操作。 在 setup线程组下提到的线程行为与普通线程组完全相同。不同的是执行顺序--- 它会在普通线程组执行之前被触发&#xff1b; 应用场景举例&#xf…

Oracle数据库笔记(一)

1.概述 Oracle版本 19c 在线迁移、自适应扫描、自适应数据共享11g 企业管理器、自动化诊断工具、自动化性能管理 Oracle特点 可用性强可扩展性强数据安全性强稳定性强 常见数据库 小 Access中 SQL Server、MySQL大 Oracle、DB2 2.数据、数据库、数据库管理系统、数据库系…

基于知识问答的上下文学习中的代码风格11.20

基于知识问答的上下文学习中的代码风格 摘要1 引言2 相关工作3 方法3.1 概述3.2 元函数设计3.3 推理 4 实验4.1 实验设置4.2 实施细节4.3 主要结果 摘要 现有的基于知识的问题分类方法通常依赖于复杂的训练技术和模型框架&#xff0c;在实际应用中存在诸多局限性。最近&#x…

redis运维(十二)

一 位图 ① 概念 1、说明&#xff1a;位图还是在操作字符串2、位图玩字符串在内存中存储的二进制3、ASCII字符通过映射转化为二进制4、操作的是字符串value ② ASCII字符铺垫 1、控制ASCII字符 2、ASCII可显示字符 ③ SETBIT 细节&#xff1a; setbit 命令的返回值是之…

算法分析与设计课后练习22

设W(5,7,10,12,15,18,20)和M35&#xff0c;使用过程SUMOFSUB找出W种使得和数等于M的全部子集并画出所生成的部分状态空间树

打破传统束缚,释放服务潜能:本地生活服务商聚合系统引领行业新风向!

本地生活服务商聚合系统是一种集合多平台、多项目的创新型服务系统&#xff0c;它打破了传统服务商系统的一对一限制&#xff0c;为创业者和运营商带来了诸多优势。小多将深入探讨本地生活服务商聚合系统的优势。 随着互联网的快速发展&#xff0c;本地生活服务也迎来了蓬勃的发…

Java实现围棋算法

围棋是一种源自中国的棋类游戏&#xff0c;也是世界上最古老、最复杂的棋类游戏之一。该游戏由黑白两方交替放置棋子在棋盘上进行&#xff0c;目的是将自己的棋子占据更多的空间&#xff0c;并将对手的棋子围死或吃掉&#xff0c;最终获得胜利。围棋不仅是一种游戏&#xff0c;…

审计dvwa高难度命令执行漏洞的代码,编写实例说明如下函数的用法

审计dvwa高难度命令执行漏洞的代码 &#xff0c;编写实例说明如下函数的用法 代码&#xff1a; <?phpif( isset( $_POST[ Submit ] ) ) {// Get input$target trim($_REQUEST[ ip ]);// Set blacklist$substitutions array(& > ,; > ,| > ,- > ,$ …

PACS系统源码,WORKLIST数字化工作流程,影像数字化存储,电子报告书写、胶片打印

PACS系统源码 可与医院HIS、LIS无缝连接 PACS系统以实现医学影像数字化存储、诊断为核心任务&#xff0c;从医学影像设备&#xff08;如CT、CR、DR、MR、DSA、RF等&#xff09;获取影像&#xff0c;集中存储、综合管理医学影像及病人相关信息&#xff0c;建立数字化工作流程。 …

Linux 环境配置小白入门

Linux从 全栈开发centOS 7 到 运维 一 Linux 入门概述1.1 操作系统1.2 Linux 简介1.3 Linux 系统组成1.4 Linux 发行版1.5 Linux 应用领域1.6 Linux vs Windows 二 虚拟机2.1 虚拟机介绍2.2 VMware WorkStation 安装2.3 VMware WorkStation 配置检查2.3 安装 CentOS 72.3.1 安装…

PIL如何批量给图片添加文字水印?

PIL如何批量给图片添加文字水印&#xff1f; 1 简单引入2 关于PIL3 本文涉及的PIL的几个类4 实现原理5 实现过程5.1 原始图片5.2 导入相关模块5.3 初始化数据5.4 水印字体设置5.5 打开原始图片并新建存储对象5.6 计算图片和水印的大小5.7 选择性设置水印文字5.8 绘制文字并设置…

ChatGPT/GPT4科研实践应用与AI绘图技术及论文高效写作

2023年随着OpenAI开发者大会的召开&#xff0c;最重磅更新当属GPTs&#xff0c;多模态API&#xff0c;未来自定义专属的GPT。微软创始人比尔盖茨称ChatGPT的出现有着重大历史意义&#xff0c;不亚于互联网和个人电脑的问世。360创始人周鸿祎认为未来各行各业如果不能搭上这班车…

高防CDN如何预防攻击?

现在网络攻击事件越来越多&#xff0c;而且愈发凶猛&#xff0c;为了保障互联网业务能稳定正常的运行&#xff0c;市场上出现了很多高防产品&#xff0c;例如高防服务器、高防IP、高防CDN等等。其中究竟高防CDN怎么防攻击&#xff0c;能防哪些攻击&#xff1f;高防CDN如何实现防…

【PostgreSQL】解决PostgreSQL时区(TimeZone)问题

问题描述 最近在使用PostgreSQL中&#xff0c;对行记录进行设置创建时间&#xff08;created_time&#xff09;时&#xff0c;出现了设置了now()时间而数据库中写入的数据是不一致的数据。 eg&#xff1a; insert into dept ( created_at, updated_at) VALUES (now(),now())…

结合两个Python小游戏,带你复习while循环、if判断、函数等知识点

&#x1f490;作者&#xff1a;insist-- &#x1f490;个人主页&#xff1a;insist-- 的个人主页 理想主义的花&#xff0c;最终会盛开在浪漫主义的土壤里&#xff0c;我们的热情永远不会熄灭&#xff0c;在现实平凡中&#xff0c;我们终将上岸&#xff0c;阳光万里 ❤️欢迎点…