【排序算法】之基数排序

一、算法介绍

基数排序是一种非比较型整数排序算法,其原理是将整数按低位到高位或者高位到低位的顺序,依次根据每一位的数值进行排序。通常情况下,基数排序会使用桶排序来处理每一位上的数值。

实现方法主要有如下:

  1. 最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。

  2. 最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

  3. 整数数据:基数排序通常用于排序整数,因为它基于整数的位数来进行排序。对于正整数和负整数,只要数据被适当地处理(例如,先将所有数转换为非负数,排序后再转换回去),也可以使用基数排序。

  4. 固定长度的字符串:如果字符串长度固定,并且字符集大小有限,则可以将每个字符视为一个“位”,类似于整数中的位,从而应用基数排序。
    时间数据:例如日期和时间,可以将其分解成不同的部分(如年、月、日、小时、分钟、秒),然后根据这些部分进行排序。

  5. 具有明确位权重的数据:基数排序适用于那些可以通过分解成几个部分,并且每个部分有明确权重的数据。例如,电话号码、邮政编码等。

  6. 数据范围不大:当数据的范围不是非常大时,基数排序能够高效工作。如果数据范围很大,那么可能需要大量的内存来存储计数数组或桶,这可能会降低算法的效率。

为了解释概念,这里通过一组正整数的数组: [53, 3, 542, 748, 14, 214, 154, 63, 616]

观察数组最大到百分位三位数字,对于那些不足百分位的,予以前缀补零处理,下面的示意图,即是按照个位、十位、百位的顺序依次排序

在这里插入图片描述
每次排序都是在前一次的结果上进行新一轮的排序换位。数字0~9即包含了每一位数上的所有可能值。问题的核心是确定最大位数,即从数组中的最大值确定,这是为了确定要进行多少轮排序,从个位,十分位,百分位…开始进行多轮排序。


二、代码实现

下面是一段代码,实现了上述数组的基数排序,采用了LSD方法,即最低位优先
核心方法是 countingSort()

package com.ds.project;import java.util.Arrays;
import java.util.OptionalInt;public class RadixSort {// 获取最大值的位数private static int getMaxDigits(int[] arr) {OptionalInt optional = Arrays.stream(arr).max();int max = 0;if (optional.isPresent()) {max = optional.getAsInt();}return (int) Math.log10(max) + 1;}// 计数排序// 该方法用于对数组中每个元素的特定位进行排序,比如个位、十位、百位等// 参数 arr: 待排序的数组 exp: 当前排序的位的权重(例如个位为1,十位为10,百位为100)private static void countingSort(int[] arr, int exp, int cycle) {int n = arr.length;// 创建一个输出数组,用于保存排序后的结果int[] output = new int[n];// 创建一个计数数组,用于统计每个数字(0-9)出现的次数int[] count = new int[10];// 初始化计数数组,确保每个数字的初始计数为0Arrays.fill(count, 0);// 遍历原数组,统计每个数字在特定位上出现的次数// 例如,对个位进行排序时,统计每个数字出现的次数for (int j : arr) {int index = (j / exp) % 10;count[index]++;}System.out.println("第" + cycle + "轮当前位数的数字权重:" + Arrays.toString(count));// 更新计数数组,使其每个索引处的值表示小于等于该索引的数字总数// 例如,count[i]现在表示小于等于i的数字总数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}System.out.println("第" + cycle + "轮统计小于每个个位数数字的计数:" + Arrays.toString(count));// 根据计数数组构建输出数组// 从后向前遍历原数组,根据每个数字在特定位上的值,将其放入输出数组的正确位置for (int i = n - 1; i >= 0; i--) {int index = (arr[i] / exp) % 10;output[count[index] - 1] = arr[i];count[index]--;}// 将排序后的结果复制回原数组// 使用System.arraycopy方法提高复制效率System.arraycopy(output, 0, arr, 0, n);}// 基数排序主函数public static void radixSort(int[] arr) {int maxDigits = getMaxDigits(arr);int cycle = 1;// 从最低位开始,逐步向最高位排序for (int exp = 1; maxDigits > 0; exp *= 10, maxDigits--) {countingSort(arr, exp, cycle);cycle++;}}// 测试基数排序public static void main(String[] args) {System.out.println(3 / 100);int[] arr = {53, 3, 542, 748, 14, 214, 154, 63, 616};System.out.println("原始数组: " + Arrays.toString(arr));radixSort(arr);System.out.println("排序后数组: " + Arrays.toString(arr));}
}

笔者在代码上下文中加了一些循环排序过程中的打印信息,有些额外的无关代码。下面对核心方法 countingSort() 进行详细解释,只列举个位数统计排序的分析内容,其他十分位,百分位上的统计排序都是类似的不再分析。

步骤 1: 初始化计数数组

首先,我们需要一个计数数组 count,用于统计每个数字(0 到 9)出现的次数。

int[] count = new int[10];  // 0 到 9 的计数数组
Arrays.fill(count, 0);      // 初始化为 0

步骤 2: 统计每个数字出现的次数

遍历原数组 arr,统计每个数字在当前位上的出现次数。

for (int j : arr) {int index = (j / exp) % 10;  // 当前位上的数字count[index]++;              // 计数
}

假设 exp = 1(即处理个位数),那么:

  • 53 的个位是 3,count[3]++,count 变为 [0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
  • 3 的个位是 3,count[3]++,count 变为 [0, 0, 0, 2, 0, 0, 0, 0, 0, 0]
  • 542 的个位是 2,count[2]++,count 变为 [0, 0, 1, 2, 0, 0, 0, 0, 0, 0]
  • 748 的个位是 8,count[8]++,count 变为 [0, 0, 1, 2, 0, 0, 0, 0, 1, 0]
  • 14 的个位是 4,count[4]++,count 变为 [0, 0, 1, 2, 1, 0, 0, 0, 1, 0]
  • 214 的个位是 4,count[4]++,count 变为 [0, 0, 1, 2, 2, 0, 0, 0, 1, 0]
  • 154 的个位是 4,count[4]++,count 变为 [0, 0, 1, 2, 3, 0, 0, 0, 1, 0]
  • 63 的个位是 3,count[3]++,count 变为 [0, 0, 1, 3, 3, 0, 0, 0, 1, 0]
  • 616 的个位是 6,count[6]++,count 变为 [0, 0, 1, 3, 3, 0, 1, 0, 1, 0]

此时 count 数组为 [0, 0, 1, 3, 3, 0, 1, 0, 1, 0]。

步骤 3: 更新计数数组

for (int i = 1; i < 10; i++) {count[i] += count[i - 1];
}

第二次遍历 count 数组,将每个位置的计数值调整为小于或等于该位置的所有数字的累计数量,这一步骤是为了确定每个数字在 output 数组中的最终位置

为什么是要统计小于等于呢?因为个位数数字可能会有重复的,所以要包含自身

count数组变成 [0, 0, 1, 4, 7, 7, 8, 8, 9, 9],索引对应的0~9,索引为2即表示个位数小于或等于2的只有一个,那么个位数是2的就是output数组的第一个元素。索引为3的表示个位数小于或等于3的有四个,去掉为2则说明个位数是3的有三个,这不好确定位置,只能保持个位数为3的元素在原始数组中的相对位置顺序,具体怎么实现请看如下步骤

步骤 4: 构建输出数组

下面循环代码是核心部分,实现了排序的稳定性和正确性

for (int i = n - 1; i >= 0; i--) {int index = (arr[i] / exp) % 10;output[count[index] - 1] = arr[i];count[index]--;}

代码是从后往前遍历原始数组的,为什么需要从后往前呢?就是为了保证当个位数的数字相同时,顺序不变化。

初始数组顺序如下:

 [53, 3, 542, 748, 14, 214, 154, 63, 616]

count计数数组为 [0, 0, 1, 4, 7, 7, 8, 8, 9, 9],

最后一位元素616的个位数字6,那么个位数字小于或者等于6的元素个数是多少呢count[6] = 8。即当前元素在整个新构建的数组output中应该排在第8的位置,索引是从下标0开始的,所以第8个元素的索引位置为7,output[7] = 616。

那为什么接着需要 count[index]-- 呢?其实是为了保证后续的个位数数字仍然为6时,能被放置在正确的位置上,即个位数都是6的元素之间位置顺序相对不移动。

上述初始数组列子改成如下:

[53, 3, 542, 748, 14, 214, 156, 63, 616]

count计数统计数组变成:[0, 0, 1, 4, 6, 6, 8, 8, 9, 9]

最后一位元素还是616,count[6] = 8,正确放置后到output数组的第8个位置,即output[7] = 616,另count[6] = count[6]-1 = 7,即往前遍历时,再遇到个位数是6的元素,比如156,那这个156元素就应该放置到第output输出数组的第7个位置,output[6] = 156。

在放置156元素之前,倒数第二个元素63放置到哪里呢?count[3] = 4,output[3] = 63,即63应放置到output输出数组的第四个位置。

从后往前遍历的作用是,可以将不同的个位数数字在初次遇到时,确定其在output输出数组中的位置,通过减少计数个数来确保再遇到相同个位数值时,它的位置能在上一次相同个位数的位置往前移动一位,从后往前遍历保证了相同个位数的相对位置保持不变。


三、拓展研究

以上数组都是正整数,那数组中包含负整数咋办呢?很简单先找出最小值,把每个元素都加上最小值的绝对值,然后进行排序,再把排序后的结果再减去原最小值的绝对值,即可得到正确的排序,以下是代码示例

 public static void main(String[] args) {System.out.println(3 / 100);int[] arr = {53, 3, -542, 748, -14, 214, 156, 63, 616};System.out.println("原始数组: " + Arrays.toString(arr));int min = getMin(arr);System.out.println("最小值:" + min);// 将数组中的元素加上最小值的绝对值,都变成正数int[] newArr = new int[arr.length];for (int i = 0; i < arr.length; i++) {newArr[i] = arr[i] + Math.abs(min);}//排序radixSort(newArr);//减去原最小值的绝对值for (int i = 0; i < arr.length; i++) {newArr[i] = newArr[i] - Math.abs(min);}System.out.println("排序后数组: " + Arrays.toString(newArr));}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

echarts实现湖南省地图并且定时轮询

1、在HTML页面引入echarts.min.js <script src"https://cdn.jsdelivr.net/npm/echarts5/dist/echarts.min.js"></script> 2、实现代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"utf-8"><…

如何搞定日语翻译?试试这四款工具

写一篇字数800-1000字的软文&#xff0c;用翻译新手的角度分享福昕翻译在线、福昕翻译客户端、海鲸AI翻译以及彩云翻译在翻译日语时候的表现&#xff0c;要求口语化表达。 最近对于一些轻小说突然感兴趣了&#xff0c;所以我开始尝试各种翻译工具来帮助我搞定日语翻译。今天&am…

仕考网:省考面试流程介绍,提前了解

省考面试流程介绍&#xff0c;一文带大家了解! 一、面试登记及抽签 考生通常需要提前10至30分钟到达指定地点进行登记。 考试工作人员核对考生身份证和面试通知书等相关证件后&#xff0c;进行抽签确定分组和进场顺序。 二、候考阶段 考生完成抽签后进入候考区等待考试。在…

【LeetCode每日一题】2024年9月第二周(上)

2024.9.9 中等 难度评分 1333 链接&#xff1a;2181. 合并零之间的节点 &#xff08;1&#xff09;题目描述&#xff1a; &#xff08;2&#xff09;示例 &#xff08;3&#xff09;分析 整体来说&#xff0c;描述还算清晰的题目&#xff0c;找到0节点所框定的区域&#xff0c…

【iOS】UIViewController的生命周期

UIViewController的生命周期 文章目录 UIViewController的生命周期前言UIViewController的一个结构UIViewController的函数的执行顺序运行代码viewWillAppear && viewDidAppear多个视图控制器跳转时的生命周期pushpresent 小结 前言 之前对于有关于UIViewControlller的…

cesium.js 入门到精通(3)

天空盒子的设置 目前的地球背景 是 地图的cesium 我们想换成自己背景 // 设置天空盒skyBox: new Cesium.SkyBox({sources: {positiveX: "./texture/sky/px.jpg",negativeX: "./texture/sky/nx.jpg",positiveY: "./texture/sky/ny.jpg",negativ…

如何构建高效快速的数据同步策略方案

在数据化的商业环境中&#xff0c;实现数据的实时同步不仅是提升企业内部协作效率的关键&#xff0c;更是确保业务决策精准性和时效性的核心要素。通过确保数据的一致性和最新性&#xff0c;企业能够实现跨部门的无缝协作&#xff0c;从而为业务流程的顺畅运作和快速响应市场变…

Linux系统部署SmartKG(知识图谱安装)

基本要求 #docker需要高版本 Docker version 20.10.14, build a224086docker 20.10.14离线安装 SmartKG官网 官方详细文档 下载部署包 SmartKG官网 准备部署 #上传到服务器 [roottest-server01 opt]# ll SmartKG-master.zip -rw-r--r-- 1 root root 79708691 Sep 11 17:4…

k8s环境搭建(续)

查看节点信息并做快照 kubectl get nodes 将components.yml文件上传到master主机 创建nginx&#xff0c;会在添加一个新的pod kubectl run nginx --imagesnginx:latest 查看nginx的pod信息 [rootk8s-master ~]# kubectl get po -Aowide|grep nginx 出现错误&#xff0c;查…

跨越技术壁垒:EasyCVR为何选择支持FMP4格式,重塑视频汇聚平台标准

随着物联网、大数据、云计算等技术的飞速发展&#xff0c;视频监控系统已经从传统的安防监控扩展到智慧城市、智能交通、工业制造等多个领域。视频流格式作为视频数据传输与存储的基础&#xff0c;其兼容性与效率直接影响到整个视频监控系统的性能。 在众多视频流格式中&#…

吴牧野与他的家首登国际家居杂志《安邸AD》秋季封面

国际钢琴艺术家吴牧野登国际一线家居杂志《安邸AD》金九秋季封面&#xff0c;首次在自己的私宅接受媒体拍摄访问&#xff0c;他的家也第一次曝光在公众面前。凭借深刻的音乐性、高超的琴技和高级感的气质&#xff0c;吴牧野打破了中国观众对钢琴家炫技派的刻板印象&#xff0c;…

携手科大讯飞丨云衔科技为企业提供全栈AI技术解决方案

作为智能时代的核心驱动力&#xff0c;人工智能不仅重塑了传统行业的面貌&#xff0c;更开辟了全新的经济增长点。科大讯飞以其深厚的技术底蕴和创新能力&#xff0c;持续引领着人工智能领域的发展潮流。云衔科技作为科大讯飞开放平台的AI技术产品线合作伙伴代理商&#xff0c;…

YOLOV8实现小目标检测

YOLOV8小目标检测 前言&#xff1a;&#xff1a; yolo版出现很多&#xff0c;基本大同小异 但是这些差异让我们考虑在实验中使用哪个版本会比较好&#xff01; 在对小目标检测的过程中&#xff0c;yolov7相比yolov8性能更加好。 如果我们还是想使用yolov8&#xff0c;也是可以实…

QImage、cv::Mat 与 HalconCpp::HObject 之间的转换

在机器视觉应用中&#xff0c;不同的图像处理库和框架常使用不同的数据结构来表示图像。常用的库包括 Qt 的 QImage、OpenCV 的 cv::Mat 以及 Halcon 的 HObject。为了在这些库之间实现无缝的数据传递和处理&#xff0c;图像格式的转换成为必不可少的环节。本文将详细介绍如何在…

再次进阶 舞台王者 第八季完美童模全球赛形象大使【许雅雯】赛场秀场超燃合集!

7月20-23日&#xff0c;2024第八季完美童模全球总决赛在青岛圆满落幕。在盛大的颁奖典礼上&#xff0c;一位才能出众的少女——许雅雯&#xff0c;迎来了她舞台生涯的璀璨时刻。 形象大使——许雅雯&#xff0c;以璀璨童星之姿&#xff0c;优雅地踏上完美童模盛宴的绚丽舞台&am…

玉米种子质量检测系统源码分享

玉米种子质量检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer…

掌握“问一问”策略,视频号流量轻松实现质的飞跃!

掌握“问一问”策略&#xff0c;视频号流量轻松实现质的飞跃&#xff01; 视频号新流量入口&#xff0c;微信问一问。如何玩转问一问功能&#xff0c;手把手操作教学。#视频号#微信#问一问#短视频#直播 市面上还有这么牛逼的一个流量隐藏入口&#xff0c;先看一下数据&#x…

微信自动回复设置真嘎嘎好用!

无论是商户、个人品牌还是普通用户&#xff0c;及时回应朋友和客户的信息至关重要。然而&#xff0c;手动一一回复既耗时又容易遗漏&#xff0c;这时&#xff0c;微信的自动回复功能就显得尤为重要。 今天&#xff0c;就教大家一招——通过个微管理系统&#xff0c;实现微信自…

2024年最新软件测试学习路线图(从入门到精通)

六维全息课程注重综合能力培养&#xff0c;从入学到职后一站式服务测试开发人才。2024年最新软件测试学习路线图&#xff0c;从入门到精通一应俱全。 9阶段专业课11大专项测试项目 适应互联网企业测试开发需求。 对于想入行学软件测试的新手来说&#xff0c;首先就需要一个高效…

如何用Docker运行Django项目

本章教程,介绍如何用Docker创建一个Django,并运行能够访问。 一、拉取镜像 这里我们使用python3.11版本的docker镜像 docker pull python:3.11二、运行容器 这里我们将容器内部的8080端口,映射到宿主机的80端口上。 docker run -itd --name python311 -p