基数排序将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后,从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始,LSD适应与那些位数较少的数字进行排序,而对于位数较多的数选择MSD效果要好,下面这个例子我是选用的LSD的排序方式
package com.lamp.sort;
import java.util.Arrays;
public class RadixSortTest {
public static void main(String[] args) {
int[] data = { 5, 20, 4, 15, 11};
printArray(data);
System.out.println("\r" + "升序排序后-------");
//数组中最多位数为2,设定基数为10进行排序
sortArrayAsc(data, 10, 2);
printArray(data);
//System.out.println("\r" + "降序排序后-------");
//数组中最多位数为2,设定基数为10进行排序
//sortArrayDesc(data, 10, 2);
//printArray(data);
}
//升幂排序
private static void sortArrayAsc(int[] data, int radix, int d) {
//定义一个临时数组大小和data数组相等
int[] temp = new int[data.length];
//定义一个位计数器,用来存放当前位的元素有多少个
int[] bucket = new int[radix];
int rate = 1;
for (int i = 0; i < d; i++) {
//将data数组中的各个元素复制到temp数组中
System.arraycopy(data, 0, temp, 0, data.length);
//将bucket数组的各个元素重置0
Arrays.fill(bucket, 0);
//当i等于0时,原数组为5, 20, 4, 15, 11,个位数的值分别为5,0,4,5,1
//此时bucket数组的值为1,1,0,,0,1,2,0,0,0,0即个位数为0,1,4的数各一个,个位数为5
//的数有两个,并将较大的数置于较后
for (int j = 0; j < data.length; j++) {
int index = (temp[j] / rate) % radix;
bucket[index] += 1;
}
//统计各元素出现位置,拿原数组来说,个位数为0的数出现了一次,位置为1,个位数为1的数也出现了
//一次,此时它的实际位置应该为自身出现个数与0出现个数之和,其余元素位置同理
//经过循环后的bucket数组为1,2,2,2,3,5,5,5,5,5
for (int j = 1; j < bucket.length; j++) {
bucket[j] = bucket[j] + bucket[j - 1];
}
for (int j = data.length - 1; j >= 0; j--) {
//当j等于data.length时,即j=4时,temp[4]=11,index的值为1,由于数组下标值比元素位置小1
//data[--2]=11,即data[1]=11,bucket[index]值减1(由于此位对应的元素已经有一个拍好了顺序)
int index = (temp[j] / rate) % radix;
data[--bucket[index]] = temp[j];
}
//一次循环过后我们可以看到data数组变为20,11,4,5,15,我们可以看到个位数字较大的数排到了较后
//接着rate乘以10并对十位进行相应排序
rate *= radix;
}
}
private static void sortArrayDesc(int[] data, int radix, int d) {
int[] temp = new int[data.length];
int[] bucket = new int[radix];
int rate = 1;
for (int i = 0; i < d; i++) {
System.arraycopy(data, 0, temp, 0, data.length);
Arrays.fill(bucket, 0);
for (int j = 0; j < data.length; j++) {
int index = (temp[j] / rate) % radix;
//降序排序最大的特点就是将位数较大的元素出现次数放在了前面
bucket[9 - index] += 1;
}
for (int j = 1; j < bucket.length; j++) {
bucket[j] = bucket[j] + bucket[j - 1];
}
for (int j = data.length - 1; j >= 0; j--) {
int index = (temp[j] / rate) % radix;
data[--bucket[9 - index]] = temp[j];
}
rate *= radix;
}
}
private static void printArray(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
}
}
分享到:
相关推荐
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
基数排序及优化java
自己写的插入排序,随机产生1000次,每次产生0-1000个数,验证算法正确性。java实现。
基数排序算法 java实现 还有基数排序的原理文档
主要介绍了Java基数排序radix sort原理及用法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
该资源提供了在Java中如何实现基数排序的全面指南。文档涵盖了基数排序的基本概念,包括如何对数组进行排序以及如何在Java中实现基数排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现基数排序,包括详细...
Java实现基数排序.rar
详解Java常用排序算法-基数排序
基数排序是一种非比较型整数排序算法,它通过按数字的各个...在Java中,基数排序的实现通常包括确定最大数的位数、对每一位进行排序、分配和收集数字等步骤。此外,为了处理负数或浮点数,可能需要在排序前进行预处理。
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
基数排序java代码,望对大家有帮助,谢谢!
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引
基数排序的关键思想是按照数字的个位、十位、百位等逐个进行计数排序,从最低位到最高位。在每个位上,使用计数排序来稳定地排序数组。通过多次迭代,对所有位进行排序后,最终得到有序的数组。 在示例代码中,我们...
java版本的基数排序,支持过程演示,支持数据编辑,插入,删除,生成随机数等功能
java各种数组排序插入交换选择归类基数排序.pdf
主要介绍了Java语言实现基数排序代码分享,具有一定借鉴价值,需要的朋友可以参考下。
八种排序算法原理及Java实现( 冒泡排序+快速排序直接插入排序+希尔排序+选择排序+归并排序+基数排序)
介绍基数排序的概念、特点、优缺点、适用场景和java代码简单实现。