基数排序基本思想 1) 将所有待比较数值统一为同样的数位长度,数位较短的数前面 补0 。然后,从 最低位 开始,依次进行一次排序。比如序列中最高位为3,那就循环3次,即个、十、百位分别比较。这样从最低位排序一直到最高位排序完成以后 , 数列就变成一个有序序列。 2) 这样说明,比较难理解,下面我们看一个图文解释,理解基数排序的步骤
代码思路
1.首先定义一个二维数组代表桶,然后定义一个一维数组记录每个桶中的元素数量
2.准备工作
2.1 计算序列中绝对值最大值的位数,以确定排序要执行多少次
2.2 取序列的最小值,从而实现对负数的桶排序
3.入、出桶 *** 作(根据最大值位数确定循环次数,每次循环时取不同的位)
3.1 遍历序列,根据元素某位的值决定它入哪个桶
3.2 记录每个桶中元素数量,方便出桶
3.3 将每个桶中的元素取出放回序列中
3.4 计数清零
3.5 重复上面 *** 作,直到每一位都比较过了
代码演示 public static Integer[] RadixSort(Integer[] arr){
Integer[][] bucket=new Integer[10][arr.length];//10个桶,放(0-9)对应位的元素
int[] bucketEleCount=new int[10];//统计每个桶放了多少元素
//1.1先看一下序列中最大值的位数,以确定排序要执行多少次,利用绝对值可以对负数长度进行计算
int max=arr[0];
int maxlength;
for(Integer e:arr){
if(Math.abs(e)>max) max=e;
}
maxlength=(Math.abs(max)+"").length();
//1.2取最小值,在后面的 *** 作中加上最小值的绝对值,从而实现对负数的桶排序
int min=arr[0];
for(Integer e:arr){
if(e
总结 1) 基数排序是对传统桶排序的扩展,速度很快 . 2) 基数排序是经典的空间换时间的方式,占用内存很大 , 当对海量数据排序时,容易造成 OutOfMemoryError 。 3) 基数排序是稳定的。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)