基数排序可以说是扩展了的桶式排序,比如当待排序列在一个很大的范围内,比如0到999999内,那么用桶式排序是很浪费空间的。而基数排序把每个排序码拆成由d个排序码,比如任何一个6位数(不满六位前面补0)拆成6个排序码,分别是个位的,十位的,百位的。。。。
排序时,分6次完成,每次按第i个排序码来排。
下面举一个例子:
如果要对6个3位整数进行排序,你会怎么做?我猜想大多数人会这样做:
123 123 123
343 135 135
362 241 241
241 343 343
135 362 352
352 352 362
先对高位进行排序,然后对高位相同的,次高位进行排序,一直进行到低位。
基数排序进行排序的方向一般有两种方式:
1) 高位优先(MSD): 从高位到低位依次对序列排序
2)低位优先(LSD): 从低位到高位依次对序列排序
计算机一般采用低位优先法(人类一般使用高位优先),
低位优先可以按照下面的一组数字做出说明:12、 104、 13、 7、 9
(1)按个位数排序是12、13、104、7、9
(2)再根据十位排序104、7、9、12、13
(3)再根据百位排序7、9、12、13、104
这里注意,如果在某一位的数字相同,那么排序结果要根据上一轮的数组确定,举个例子来说:07和09在十分位都是0,但是上一轮排序的时候09是排在07后面的;同样举一个例子,12和13在十分位都是1,但是由于上一轮12是排在13前面,所以在十分位排序的时候,12也要排在13前面。
所以,一般来说,10基数排序的算法应该是这样的?
(1)判断数据在各位的大小,排列数据;
(2)根据1的结果,判断数据在十位的大小,排列数据。如果数据在这个位置的余数相同,那么数据之间的顺序根据上一轮的排列顺序确定;
(3)依次类推,继续判断数据在百位、千位......上面的数据重新排序,直到所有的数据在某一位上数据都为0。
基数排序一般借助桶式排序,每次按第N位排序时,采用桶式排序。对于如何安排每次落入同一个桶中的数据有两种安排方法:
1)顺序存储:每次使用桶式排序,放入r个桶中,相同时增加计数。
2)链式存储:每个桶通过一个静态队列来跟踪。
import java.util.Arrays;
public class RadixSort{
//基于桶排序的基数排序算法
private static void radixSort(int[] array,int radix, int distance) {
//array为待排序数组
//radix,代表基数 (桶的个数)
//代表排序元素的位数
int length = array.length;
int[] temp = new int[length];//用于暂存元素
int[] count = new int[radix];//用于桶排序
int divide = 1;
for (int i = 0; i < distance; i++) {
System.arraycopy(array, 0,temp, 0, length);
Arrays.fill(count, 0);
for (int j = 0; j < length; j++) {
int tempKey = (temp[j]/divide)%radix;
count[tempKey]++;
}
for (int j = 1; j < radix; j++) {
count [j] = count[j] + count[j-1];
}
//重点在下面这个方法
for (int j = length - 1; j >= 0; j--) {
int tempKey = (temp[j]/divide)%radix;
count[tempKey]--;
array[count[tempKey]] = temp[j];
}
divide = divide * radix;
}
}
public static void main(String[] args) {
int[] array = {3,2,3,2,5,333,45566,2345678,78,990,12,432,56};
radixSort(array,10,7);
for (int i = 0; i < array.length; i++) {
System.out.print(" " + array[i]);
}
}
}
源码下载:
分享到:
相关推荐
包括了基数排序的实现代码和流程图。 先对个位数字进行统计,然后根据个位进行排序,然后对十位进行统计,然后根据十位进行排序,即可获得最终结果。 时间效率:待排序列为n个记录,10个关键码,关键码的取值范围为0...
基数排序基数排序基数排序基数排序基数排序
数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序数据结构基数排序
数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序数据结构之基数排序
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
基数排序法用链表完成使用C语言适用于刚入门的学者
基数排序过程及程序基数排序过程及程序基数排序过程及程序基数排序过程及程序
这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶...
基数排序C语言实现
1.需求分析 ①.问题描述 给出一组数据,按照最低位优先的方法完成基数排序。多关键码排序按照从最主位关键码到最次位或从最次位到最主位关键码的顺序逐次排序。
基数排序算法 java实现 还有基数排序的原理文档
插入排序 冒泡排序 堆排序 基数排序 选择排序 快速排序的源码 java实现
排序算法很多,下面有基数排序,堆排序,希尔排序,直接插入排序的代码和思路
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
8646 基数排序 时间限制:1000MS 内存限制:1000K 提交次数:0 通过次数:0 题型: 编程题 语言: 无限制 描述 用函数实现基数排序,并输出每次分配收集后排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二...
Radix Sort (基数排序)排序算法
基数排序算法,这是分不错的算法,实现起来有点难,用静态链表实现,每次改变结点的指向,希望有用,多多指教
网上的一些基数排序都是用链表的,写了个非链表的例子
排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...
常用排序效率PK 冒泡 快排 选择排序 基数排序 希尔排序 折半插入排序 等