在众多的排序方法中基数排序比较特殊,它是一种不需要进行关键字之间比较的排序方法,利用多关键字的划分,逐渐将待排序列排好序。
举个例子:
现在有数组:278,109,63,930,589,184,505,269,8,83
第一次根据各位数将数组划分为10个队列(当然其中的某些队列可能不含有元素)
0:930
1:
2:
3:63,83
4:184
5:505
6:
7:
8:278,8
9:109,589,269
然后收集成序列:
930,63,83,184,505,278,8,109,589,269
在进行第二次分组:
0:505,8,109
1:
2:
3:930
4:
5:
6:63,269
7:278
8:83,184,589
9:
第二次收集:
505,8,109,930,63,269,278,83,184,589
第三次分配:
0:8,63,83
1:109,184
2:278,269
3:
4:
5:505,589
6:
7:
8:
9:930
最后得到序列:
8,63,83,109,184,269,278,505,589,930
完成排序!
基数排序其实是利用多关键字先达到局部有序,再调整达到全局有序。
public static void radixSort(int[] array){
//首先确定排序的趟数;
int max=array[0];
for(int i=1;i<array.length;i++){
if(array[i]>max){
max=array[i];
}
}
int time=0;
//判断位数;
while(max>0){
max/=10;
time++;
}
//建立10个队列;
LinkQueue<Integer>[] queue=new LinkQueue[10];
for(int i=0;i<10;i++){
queue[i]=new LinkQueue<Integer>();
}
//进行time次分配和收集;
for(int i=0;i<time;i++){
//分配数组元素;
for(int j=0;j<array.length;j++){
//得到数字的第time+1位数;
queue[array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i)].enQueue(array[j]);
}
int count=0;//元素计数器;
//收集队列元素;
for(int k=0;k<10;k++){
while(queue[k].size()>0){
array[count]=(Integer) queue[k].deQueue().getElement();
count++;
}
}
}
}
如果待排序列的关键字不是自然数,我们当然可以对其进行转化,然后利用类似的方式排序。
<!--EndFragment-->
分享到:
相关推荐
Java实现基数排序.rar
基数排序是一种非比较型整数排序算法,它通过按数字的各个...在Java中,基数排序的实现通常包括确定最大数的位数、对每一位进行排序、分配和收集数字等步骤。此外,为了处理负数或浮点数,可能需要在排序前进行预处理。
基数排序的关键思想是按照数字的个位、十位、百位等逐个进行计数排序,从最低位到最高位。在每个位上,使用计数排序来稳定地排序数组。通过多次迭代,对所有位进行排序后,最终得到有序的数组。 在示例代码中,我们...
基数排序算法 java实现 还有基数排序的原理文档
该资源提供了在Java中如何实现基数排序的全面指南。文档涵盖了基数排序的基本概念,包括如何对数组进行排序以及如何在Java中实现基数排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现基数排序,包括详细...
自己写的插入排序,随机产生1000次,每次产生0-1000个数,验证算法正确性。java实现。
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
主要介绍了Java语言实现基数排序代码分享,具有一定借鉴价值,需要的朋友可以参考下。
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
八种排序算法原理及Java实现( 冒泡排序+快速排序直接插入排序+希尔排序+选择排序+归并排序+基数排序)
八大排序java实现版本,直接插入排序、折半插入排序、冒泡排序、简单选择排序、希尔插入排序、快速排序 、堆排序、2-路归并排序 、基数排序,并有时间比较,博文...
介绍基数排序的概念、特点、优缺点、适用场景和java代码简单实现。
平日所见的基数排序基本都是讲正整数的,没有讲到负数的,所以今天写一个可解决负数情况的基数排序。 首先,我们可以加上某个值,使得数组中肯定不会出现负数,然后这样我们就可以按照以前基数排序的套路进行排序了...
用java实现了10种基础排序,其内容包括: 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.桶排序 9.基数排序 10.计数排序 如有疑问请私信我
几种内部排序算法的Java实现 各种内部排序方法的比较 直接插入排序 折半插入排序 希尔排序 起泡排序 快速排序 简单选择排序 树形选择排序 堆排序 归并排序 基数排序
主要介绍了基数排序简介及Java语言实现,涉及基数排序的基本思想简单介绍和桶排序的分析,以及基数排序的Java实现,具有一定借鉴价值,需要的朋友可以参考下。
冒泡排序,插入排序,希尔排序,选择排序,堆排序,归并排序,快速排序,桶排序,计数排序,基数排序,TimeSort排序
Java中常见的排序算法 1.直接插入排序 2.希尔排序 3.选择排序 4.冒泡排序 5.归并排序 6.快速排序 7.堆排序 8.计数排序 9....基数排序 ...包含这十种算法的讲解以及动态图解(ppt)和java实现
以下排序的Java代码实现: 插入排序(直接插入排序、二分法插入排序、希尔排序) 选择排序(简单选择排序、堆排序) 交换排序(冒泡排序、快速排序) 归并排序 基数排序
Java实现八大排序算法,算法描述以及代码实现, 1. 直接插入排序 2. 希尔排序 3. 简单选择排序 4. 堆排序 5. 冒泡排序 6. 快速排序 7. 归并排序 8. 基数排序