算法回顾系列第八篇:基数排序
--------------------------------
基数排序
基本原理:
顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用。
基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。
程序实现:
/**
* RadixSort:
* 分为LSD(Least significant digital)或MSD(Most significant digital),
* LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始.
*/
public class RadixSort{
/**
* LSD方式(由键值的最右边开始)
* 由于先做了低位的排序,所以当高位相等时,低位数字还是由小到大的顺序入桶的,就是说入完桶还是有序的.
* @param 待排序数组
* @param 桶个数(即Hash后存在多少种情况),此处因为是数字,所以共需要0-9个桶.
*/
public static void lsdSort(int[] number,int d){
//temp[桶个数][桶内元素个数](桶内元素最多可能是全部元素)
int[][] temp = new int[d][number.length];
//每个桶内元素的计数
int[] order = new int[d];
int maxLength = getMaxNumberLength(number);//该数组内元素的最大位数.
int current=1;//控制键值排序依据哪一位(LSD从最右起).
int currentValue=1;//位数代表的值(1-个位,10-十位,100-百位...)
int k=0;//用于标记将桶内元素复制到数组中的位置.
while(current <= maxLength) {
System.out.println("********************");
System.out.println("当前位:"+current+" 代表值:"+currentValue);
System.out.println("入桶:");
for(int i = 0; i < number.length; i++){
//Hash取放入哪个桶:除以所在位数值,再与桶总数取模(即第几个桶).
int lsd = ((number[i] / currentValue) % d);
//放入桶内哪个位置采用计数法.
temp[lsd][order[lsd]] = number[i];
//放入桶后该桶内元素计数加1.
order[lsd]++;
}
System.out.println("各桶内元素分布:"+Arrays.deepToString(temp));
System.out.println("各桶内元素计数:"+Arrays.toString(order));
System.out.println("出桶:");
for(int i = 0; i < d; i++){//顺序遍历各桶.
if(order[i] != 0){//如果桶内元素个数不为0.
for(int j = 0; j < order[i]; j++) {//遍历当前桶内元素.
number[k] = temp[i][j];//将当前桶内元素整理到数组中.
k++;//标记位右移;
temp[i][j]=0;//复制后桶内元素清0.
}
}
order[i] = 0;//每个桶内元素复制完后,桶内元素计数清0.
}
System.out.println("本趟出桶整理后:"+Arrays.toString(number));
current++;
currentValue *= 10;//LSD方式每左移一位,该位代表的值*10.
k = 0;//每趟复制结束后,标记位归0.
}
}
/**
* 取数组内元素的最大长度
*/
public static int getMaxNumberLength(int[] number){
int maxLength = 1;//最大数字长度
for(int i=0;i<number.length;i++){
int length;//当前数字长度
int k=1;//倍数
//每次循环递增10倍,一直除到0为止.
for(length=0;(number[i]/k)>0;length++){
k*=10;
}
if(length>maxLength){
maxLength=length;
}
}
return maxLength;
}
public static void main(String[] args) {
int[] data = new int[]{73,22,93,43,55,14,28,65,39,81,33,100,6};
RadixSort.lsdSort(data, 10);
System.out.println("Result:"+Arrays.toString(data));
}
}
上面程序中:
从右向左依次作为排序依据位放入桶中,并记录每个桶内的元素个数。
然后,按桶的顺序将桶内元素写入排序数组内。
依此类推,直到最高位完成排序。
由于先做了低位的排序,所以当高位相等时,低位数字还是由小到大的顺序入桶的,就是说入完桶还是有序的。
性能分析:O(d(n+radix)),n个记录,d个关键码,关键码的取值范围为radix.
空间复杂度:O(n)
稳定性:稳定。
分享到:
相关推荐
6.5.2 基数排序 6.5.3 凸包 6.5.4 并查集 第7章 数组和矩阵 7.1 数组 7.1.1 抽象数据类型 7.1.2 C++数组的索引 7.1.3 行主映射和列主映射 7.1.4 用数组的数组来描述 7.1.5 行主描述和列主描述 7.1.6 不规则二维数组 ...
06-003习题课:栈的基本操作、KMP算法回顾 06-004二叉树的定义、性质与存储结构 06-005二叉树的前序、中序和后序遍历的递归与非递归算法 06-006统计二叉树中叶子结点个数、按给定的先序序列建立二叉链表 06-007线索...
3.8.2 基数排序 116 3.8.3 等价类 117 3.8.4 凸包 122 3.9 参考及推荐读物 127 第4章 数组和矩阵 128 4.1 数组 128 4.1.1 抽象数据类型 128 4.1.2 C++数组 129 4.1.3 行主映射和列主映射 129 4.1.4 类Array1D 131 ...
leetcode叫数 结构 list 链表 recursive 递归 sort 排序 stack 栈 ...需要回顾 ...冒泡和选择排序不要混淆了,插入排序...基数排序:基数排序要求数据可以划分成高低位,位之间有递进关系,用稳定排序算法依次按低位到高位排
内容:搜索算法线性搜寻二进制搜索三元搜索排序算法气泡排序选择排序插入排序合并排序快速分类基数排序Bogo排序最短路径算法迪克斯特拉弗洛伊德·沃沙尔通用数据结构堆队列叠数组链表使用的语言: C ++ PythonJavaC ...
简单算法 关于 简短的算法回顾使用Java,包括在最佳和最差情况下每种算法的步骤数,时间复杂度和运行时间。 演算法 快速排序 合并排序 堆排序 气泡排序 插入排序 选择排序 基数排序 Timsort
3.8.2 基数排序 116 3.8.3 等价类 117 3.8.4 凸包 122 3.9 参考及推荐读物 127 第4章 数组和矩阵 128 4.1 数组 128 4.1.1 抽象数据类型 128 4.1.2 C++数组 129 4.1.3 行主映射和列主映射 129 4.1.4 类Array1D 131 ...
基数排序 插入排序 TODO:尾调用优化空间? 大型系统分布式系统 不同排序算法的比较 问题: nodejs 中可能存在 ** 兼容性问题 类别: 树动态规划回溯 排序图 学习资源 动态规划 涵盖的问题 二维 DP 濒海战斗舰 给定...
3.8.2 基数排序 116 3.8.3 等价类 117 3.8.4 凸包 122 3.9 参考及推荐读物 127 第4章 数组和矩阵 128 4.1 数组 128 4.1.1 抽象数据类型 128 4.1.2 C++数组 129 4.1.3 行主映射和列主映射 129 4.1.4 类Array1D 131 ...
11.2.3 基数排序 319 11.3 各种排序算法的比较 321 C++片段4 类关系和重用 325 C4.1 回顾继承 326 C4.1.1 类的公有、私有和受保护部分 331 C4.1.2 公有、私有和受保护继承 332 C4.1.3 is-a和as-a关系 333 C...