Java数据结构与算法(排序)——基数排序(LSD)

Java数据结构与算法(排序)——基数排序(LSD)一、基本思想先从最低位开始排序,再对次低位排序,直到对最高位排序后得到一个有序序列(位数不同时高位补0)。二、举例分析假设有一串数列:73,22,93,43,55,14,28,65,39,81。排序过程如下:(1)先根据个位进行排序,得到:0——1——812——223——73,93,434——145——55,656——7——8——289——39(2…

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

一、基本思想

最低位优先法,LSD(Least significant digital)—— 先从最低位开始排序,再对次低位排序,直到对最高位排序后得到一个有序序列(位数不同时高位补 0)。

二、举例分析

假设有一串数列:73, 22, 93, 43, 55, 14, 28, 65, 39, 81。排序过程如下:
(1)先根据个位进行排序,得到:
0——
1——81
2——22
3——73,93,43
4——14
5——55,65
6——
7——
8——28
9——39
(2)将按个位排序的结果整理得到新数列:81, 22, 73, 93, 43, 14, 55, 65, 28, 39。再根据十位进行排序,得到:
0——
1——14
2——22,28
3——39
4——43
5——55
6——65
7——73
8——81
9——93
(3)将按十位排序的结果整理得到新数列:14, 22, 28, 39, 43, 55, 65, 73, 81, 93。这时数列已经有序。若数列中有三位数以上,则再根据百位进行排序,以此类推,直至最高位为止。

三、代码实现

public int[] radixSort(int[] sourceArray){ 

// 复制数组
int[] array = Arrays.copyOf(sourceArray, sourceArray.length);
// 找数组中的最大值
int maxValue = array[0];
for (int i = 1; i < array.length; i++) { 

if(maxValue < array[i])
maxValue = array[i];
}
// 最大值的位数
double d = Math.pow(10, String.valueOf(maxValue).length());
int k = 1;
int[][] t = new int[10][array.length];// 桶,0~9共十位,创建十个桶;
int[] num = new int[10];// 记录每个桶中存入数的个数
while(k < d){ 

// 按位存入桶中:k = 1时,按个位;k = 10时,按十位……
for(int a : array){ 

int m = (a / k) % 10;
t[m][num[m]] = a;
num[m]++;
}
// 从桶中取出放回array。k=1时,是按个位排序的结果;k=10时,是按十位排序的结果……
int c = 0;
for (int i = 0; i < 10; i++) { 

if(num[i] != 0){ 

for (int j = 0; j < num[i]; j++) { 

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

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

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

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

(0)


相关推荐

  • 边缘人的TechEd2006

    边缘人的TechEd2006

  • 《深入解析IPv6(第3版)》——第10章 IPv6路由选择10.1 IPv6中的路由选择

    《深入解析IPv6(第3版)》——第10章 IPv6路由选择10.1 IPv6中的路由选择

  • jboss安装与配置_微信最新版下载并安装

    jboss安装与配置_微信最新版下载并安装jboss有开源和商业两个版本,他们区别如下:JBossAS开源社区版本,发布比较频繁。JBoss7,先后发布了7.0.0,7.0.1,7.0.2,7.1.0,7.1.1,7.1.2,7.1.3,7.2.0,其中7.1.1比较经典,7.2.0是JBossEAP6.1的基础,但7.1.2,7.1.3,7.2.0只是源代码打了Tag,并没提供开放下载。JBossEAP(EnterpriseApplicationPlatform)在开源版本上构建的企业版本,目

  • AVAudioEngine录音崩溃, reason: ‘format.sampleRate == hwFormat.sampleRate

    AVAudioEngine录音崩溃, reason: ‘format.sampleRate == hwFormat.sampleRateAVAudioEngine录音频时偶发崩溃报错信息大致如下:2021-12-1520:12:38.429028+0800*[1659:708511]NSURLConnectionfinishedwitherror-code-1002″AudioRecorder创建Audio缓存文件夹成功/var/mobile/Containers/Data/Application//Library/Caches/Audio”2021-12-1520:13:30.762736+0800***

    2022年10月17日
  • 不要看《深入浅出MFC》![通俗易懂]

    不要看《深入浅出MFC》![通俗易懂]   开篇先声明一点,《深入浅出MFC》是一本不错的书,对于MFC原码的剖析,十分到位,特别是前面对于MFC六大关键技术的总结和演示程序,尤其精彩。那为什么我要说不要看这本书呢?   我是站在一个初学者的角度来说这句话的,也是我当初看了这本书的一些感受(因为过于难以理解,差了几章没有看,后来再补的),这本书对于MFC的讲解对一个初次接触MFC的人来说,内容过于的晦涩难懂,大段大段的原码引用,一

  • 三极管的使用方法,放大,截止,饱和[通俗易懂]

    三极管的使用方法,放大,截止,饱和[通俗易懂]1.首先认识清楚三极管的管脚                       参考资料万用表区分mos管引脚2.知道管脚我们也就知道NPN和PNP了,箭头朝内PNP,导通电压顺箭头过,电压导通,电流控制。那箭头朝外的自然就是NPN了!NPN管工作在放大区的时候:集电极电压&gt;基极电压&gt;发射极电压也就是:Vc&gt;Vb&gt;Ve …

发表回复

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

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