数据结构Java版之基数排序(四)
2024-10-21 18:37:30
基数排序:
基数排序分为两种:第一种是LSD ,从最低位开始排序, 第二种是 MSD 从最高位开始排。这里介绍第一种LSD排序算法。
首先,我们先了解什么是基数。基数是根据具体的排序情况而定的,比如我们常见的基数是十进制-10,还有二进制-2。
其次,要熟记基数排序的思想:通过对每一个位上的值相排序,就可以完成对整个数组的排序。
基数排序的算法实现流程:遍历所有数组元素,找出元素最大的位值 -------->从低位到高位把数组元素上的位值存入链表中-------->遍历所有链表,将链表里面的值重新赋值给数组,再情况链表。
例如:对数组 int[ ] data = {421, 240, 35, 532, 305, 430, 124};进行排序,首先我们要做的是对个位上的数值进行排序。
第一遍排序的结果为: 240 430 421 532 124 35 305
再进行十位上的数值排序:
第二遍排序的结果为: 305 421 124 430 532 35 240
再进行百位上的数值排序:
第三遍排序的结果为: 35 124 240 305 421 430 532
最后我们的到的排序结果就是: 35 124 240 305 421 430 532
至此,已经完成了对数组的排序
附源码:
public class RadixSort {
@Test
public void fun() {
int[] n = {421, 240, 35, 532, 305, 430, 124};
radixSort(n);
for(int i : n) {
System.out.print(i + " ");
}
}
//实现基数排序 LSD-从最低位开始排 MSD-从最高位开始排
public void radixSort(int[] data) {
int maxBin = maxBin(data);
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0; i < 10; i ++) {
list.add(new ArrayList<Integer>());
}
for(int i = 0, factor = 1; i < maxBin; factor *= 10, i ++) {
for(int j = 0; j < data.length; j ++) {
list.get((data[j]/factor)%10).add(data[j]);
}
for(int j = 0, k = 0; j < list.size(); j ++) {
while(!list.get(j).isEmpty()) {
data[k] = list.get(j).get(0);
list.get(j).remove(0);
k ++;
}
}
}
}
//计算数组里元素的最大位数
public int maxBin(int[] data) {
int maxLen = 0;
for(int i = 0; i < data.length; i ++) {
int size = Integer.toString(data[i]).length();
maxLen = size > maxLen ? size : maxLen;
}
return maxLen;
}
}
最新文章
- 使用ping钥匙临时开启SSH:22端口,实现远程安全SSH登录管理就这么简单
- python_way,day8 面向对象【多态、成员--字段 方法 属性、成员修饰符、特殊成员、异常处理、设计模式之单例模式、模块:isinstance、issubclass】
- 算法练习1 用c#编写的一个判定一组数是否是有序的
- linux清除swap
- JavaScript创建命名空间、类及类成员
- 一天一个Java基础——序列化
- 配置tomcat时踩过的坑
- JSON基础知识总结
- MySQL保留关键字
- 使WiFi具有保存历史连接的功能
- MyEclipse去除网上复制下来的代码带有的行号
- 本地git部署web连接azure的git存储库
- 修真院java后端工程师学习课程--任务1(day one)
- ";未找到应用程序的“aps-environment”的权利字符串";
- __init__、__new__、__call__ 方法
- python 学习 面向对象编程
- webvtt字幕转srt字幕的python程序(附改名程序)
- k8s学习-资源管理
- Educational Codeforces Round 25 E. Minimal Labels&;&;hdu1258
- python 将日期戳(五位数时间)转换为标准时间