基数排序(LSD+MSD)详解

基数排序(LSD+MSD)详解一.计数排序二.基数排序

大家好,又见面了,我是你们的朋友全栈君。

基数排序

分为两类:

第一类:最低位优先法,简称LSD法:先从最低位开始排序,再对次低位排序,直到对最高位排序后得到一个有序序列;具体过程如下图所示:

初始数组序列为:15,25,105,78,34,21,32,41,按照个位数大小依次入桶;

基数排序(LSD+MSD)详解

将桶中数依次倒出,对于同一个桶中的数按先进先出顺序倒出,结果为:21,41,32,34,15,25,105,78,再按十位数大小依次入桶;

基数排序(LSD+MSD)详解

将桶中数依次倒出,结果为:105,15,21,25,32,34,41,78,再按百位上数大小依次入桶,没有百位的数则按百位为0入桶;

基数排序(LSD+MSD)详解

将桶中数倒出,结果为:15,21,25,32,34,41,78,105

Java实现代码如下:

public void radixSort(int[] A,int n){
		int max = A[0];
		for(int i = 1 ;i < n;i++){
			if(max < A[i])
				max = A[i];
		}
		double d = Math.pow(10, String.valueOf(max).length());
		
		int k = 1;
		int[][] t = new int[10][n];  //桶
		int[] num = new int[n];  //记录每个桶中存入数的个数
		while(k < d){
			for(int a : A){
				int m = (a / k) % 10;
				t[m][num[m]] = a;
				num[m]++;
			}
			int c = 0;
			for(int i = 0; i < n; i++){
				if(num[i] != 0){
					for(int j = 0;j < num[i];j++){
						A[c++] = t[i][j];
					}
				}
				num[i] = 0;
			}
			k = k * 10;
		}
		
	}

第二类:最高位优先法,简称MSD法:先从最高位开始排序,再逐个对各分组按次高位进行子排序,循环直到最低位。

仍以序列:15,25,105,78,34,21,32,41为例,从最高位百位依次入桶,只有105有百位,其他百位按0算;检测每个桶中的数据。当桶中的元素个数多于1个的时候,要对这个桶递归进行下一位的分组。

基数排序(LSD+MSD)详解

Java代码实现:

public class MSDSort {
	public int[] sort(int[] A, int n){
		int max = A[0];
		for(int i = 1 ;i < n;i++){
			if(max < A[i])
				max = A[i];
		}
		int maxL = String.valueOf(max).length();  //获取数组中最长元素长度
		
		int k = new Double(Math.pow(10, maxL - 1)).intValue();
		int[][] t = new int[10][n];  //桶
		int[] num = new int[n];      //记录每个桶中存入数的个数
		
		for(int a : A){              //按最高位入桶
			int m = (a / k) % 10;
			t[m][num[m]] = a;
			num[m]++;
		}
		int c = 0;
		for(int i = 0; i < n; i++){
			if(num[i] == 1){        //如果桶中只有一个数则直接取出
				A[c++] = t[i][0];
			}else if(num[i] > 1){   //如果桶中不止一个数,则另存如数组B递归
				int[] B = new int[num[i]]; 
				for(int j = 0;j < num[i];j++){
					B[j] = t[i][j];
					sort(B,num[i]);   //递归方法
				}
			}
		}
		return A;
	}
	public static void main(String[] args) {
		RadixSort r = new RadixSort();
		int[] A = {12,1,23,123,34};
		r.sort(A, A.length);
		for(int a : A){
			System.out.println(a);
		}

	}

}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/133297.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Oracle insert all 详解

    Oracle insert all 详解文章目录1概述2insert的两种形式2.1insertfirst2.2insertall3数据一致性(同时插入)2.1验证:insertinto数据不一致2.2验证:insertall数据一致1概述1.作用:’正确、高效’的将’同一批数据’插入至’不同的表’中2.好处(1)’正确’:避免数据差异(2)’高效’:优于写多个insertinto(因为无论插入多少张表,’主表’只会被读取一次)3.场景,若需求:将表t中

  • git fetch 和git pull 的差别

    git fetch 和git pull 的差别

  • 安装Luma QQ (LINUX)

    安装Luma QQ (LINUX)

  • bios刷写工具_蓝天P750/P751编程器刷BIOS「建议收藏」

    bios刷写工具_蓝天P750/P751编程器刷BIOS「建议收藏」神舟ZX8-SP7是蓝天P751DM2模具,今天在WIN下刷BIOS成功刷黑,开始使用编程器刷BIOS,笔记本BIOS芯片由于是焊在主板上必须用夹子或者脱焊后用烧录座刷写,所以需要买编程器夹子。工具:优硕EZP-XPROV2、优硕SOP8编程器夹子。目标:神舟ZX8-SP7(P751DM2模具)准备工作:去蓝天镜像站下载对应的模具的BIOS蓝天镜像站:https://repo.palkeo.co…

  • tcpdump抓包命令怎么用_linux系统抓包工具

    tcpdump抓包命令怎么用_linux系统抓包工具今天要给大家介绍的一个Unix下的一个网络数据采集分析工具,也就是我们常说的抓包工具。与它功能类似的工具有wireshark,不同的是,wireshark有图形化界面,而tcpdump则只有命令行。由于我本人更习惯使用命令行的方式进行抓包,因此今天先跳过wireshark,直接给大家介绍这个tcpdump神器。这篇文章,我肝了好几天,借助于Linux的man帮助命令,我把tcpdump的用法全部研究了个遍,才形成了本文,不夸张的说,应该可以算是中文里把tcpdump.

    2022年10月14日
  • linux下vsftpd架设ftp服务器「建议收藏」

    linux下vsftpd架设ftp服务器「建议收藏」1.sudoapt-getinstallvsftpd2.使用netstat-tnl可以查看是否打开了21端口。是否有这行:tcp000.0.0.0:210.0.0.0:*LISTEN3.用浏览器访问一下吧ftp://10.45.7.25安装完毕后,匿名用户可以正常访问ftp具体配置参见:原文地址:http://…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号