摘要:本文主要向大家介绍了JAVA语言编程开发基数排序解析,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。
本文主要向大家介绍了JAVA语言编程开发基数排序解析,通过具体的内容向大家展示,希望对大家学习JAVA语言有所帮助。
1.桶式排序概念
有限个数字m,每个数字的大小都在1与n之间,则我们可以假设有n个桶,遍历m个数字,
将其存入对应的桶中(如数字的值为3,就存入3号桶,桶的值对应存入数字的个数)
2.基数排序概念
基于桶式排序,将要排序的数字一位一位的比较,经历多次桶式排序,得出最终的序列
如果要排序的元素可以分成多位,并且每一位都在一个固定的范围内,则可以用这种排序方法,如对10进制数字的排序
3.代码实现
/**
* 桶式排序
* max是最大数字
* @param arr
* @param max
*/
public void bucketSort(int[] arr,int max){
//声明一个数组,这就是桶,编号从0到max的桶,一共max+1个
int[] count = new int[max + 1];
//遍历数组,用桶计数
for(int i = 0;i < arr.length;i++){
count[arr[i]]++;
}
int k = 0;
for(int i = 0;i <=max ;i++){
while(count[i] > 0){
arr[k++] = i;
count[i]--;
}
}
System.out.println("排序后");
printArr(arr);
}
/*
* 基数排序 稳定的排序算法
* array 代表数组
* radix 代表基数
* d 代表排序元素的位数
*/
public int[] radixSort1(int[] arr, int radix, int d){
//第一维radix表示一共有radix个桶
//第二维arr.length表示每个桶最多可能存放a.length个数字
int[][] temp = new int[radix][arr.length];
// count用于记录待排序元素的信息,用来表示该位是i的数的个数
int[] count = new int[radix];
// 定义每一轮的除数,1,10,100...
int rate = 1;
for (int i = 0; i < d; i++) {
System.out.println("第"+(i+1)+"次排序前");
printArr(arr);
System.out.println("除数 :"+rate);
//遍历要排序的数组,将其存入temp数组中(按照第n位上的数字将数字放入桶中)
for (int j = 0; j < arr.length; j++) {
//取余
int subKey = (arr[j] / rate) % 10;
//System.out.println("sub : count "+ subKey+" : "+count[subKey]);
temp[subKey][count[subKey]++] = arr[j];
}
int m = 0;//arr数组下标
//把每趟整理的数值按整理后的顺序放到原数组中, 进行下次循环排序
for (int j = 0; j < radix; j++) {
//该号桶个数大于0
if(count[j] != 0){
System.out.println("桶号:"+j+" 第"+j+"号桶的个数"+count[j]);
for (int k = 0; k < count[j]; k++) {
arr[m++] = temp[j][k];
}
//把相应位上的个数置空,下次使用
count[j] = 0;
}
}
rate = rate * 10;
System.out.println("第"+(i+1)+"次排序后");
printArr(arr);
System.out.println();
}
return arr;
}
4.测试
@Test
public void test(){
//int arr[] = {0,1,1,2,3,3,4,8,7,6,12,22,65};
int arr[] = { 1200, 292, 121, 72, 233, 44, 12 };
//int arr[] = {6,3,8,2,9,1};
System.out.println("排序前");
printArr(arr);
int[] data = radixSort1(arr,10,4);
System.out.println("排序后");
printArr(data);
}
public void printArr(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
5.总结
算法特点:
1.是稳定排序
2.可用于链式结构,也可用于顺序结构
3.时间复杂度可以突破基于关键字比较一类方法的下界O(nlog2n),达到O(n)
4.基数排序使用条件有严格的要求:需要知道各级关键字的主次关系和各级关键字的取值范围。
本文由职坐标整理并发布,希望对同学们有所帮助。了解更多详情请关注编程语言JAVA频道!
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了,明天再试试吧!
我们会在第一时间安排职业规划师联系您!
您也可以联系我们的职业规划师咨询:
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com,All Rights Reserved.
沪公网安备 31011502005948号