大家好，又见面了，我是你们的朋友全栈君。
基数排序
分为两类：
第一类：最低位优先法，简称LSD法：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；具体过程如下图所示：
初始数组序列为：15,25,105,78,34,21,32,41，按照个位数大小依次入桶；
将桶中数依次倒出，对于同一个桶中的数按先进先出顺序倒出，结果为：21,41,32,34,15,25,105,78，再按十位数大小依次入桶；
将桶中数依次倒出，结果为：105,15,21,25,32,34,41,78，再按百位上数大小依次入桶，没有百位的数则按百位为0入桶；
将桶中数倒出，结果为：15,21,25,32,34,41,78,105
Java实现代码如下：
public void radixSort(int[] A,int n){
int max = A[0];
for(int i = 1 ;i < n;i++){
if(max < A[i])
max = A[i];
}
double d = Math.pow(10, String.valueOf(max).length());
int k = 1;
int[][] t = new int[10][n]; //桶
int[] num = new int[n]; //记录每个桶中存入数的个数
while(k < d){
for(int a : A){
int m = (a / k) % 10;
t[m][num[m]] = a;
num[m]++;
}
int c = 0;
for(int i = 0; i < n; i++){
if(num[i] != 0){
for(int j = 0;j < num[i];j++){
A[c++] = t[i][j];
}
}
num[i] = 0;
}
k = k * 10;
}
}
第二类：最高位优先法，简称MSD法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。
仍以序列：15,25,105,78,34,21,32,41为例，从最高位百位依次入桶，只有105有百位，其他百位按0算；检测每个桶中的数据。当桶中的元素个数多于1个的时候，要对这个桶递归进行下一位的分组。
Java代码实现：
public class MSDSort {
public int[] sort(int[] A, int n){
int max = A[0];
for(int i = 1 ;i < n;i++){
if(max < A[i])
max = A[i];
}
int maxL = String.valueOf(max).length(); //获取数组中最长元素长度
int k = new Double(Math.pow(10, maxL - 1)).intValue();
int[][] t = new int[10][n]; //桶
int[] num = new int[n]; //记录每个桶中存入数的个数
for(int a : A){ //按最高位入桶
int m = (a / k) % 10;
t[m][num[m]] = a;
num[m]++;
}
int c = 0;
for(int i = 0; i < n; i++){
if(num[i] == 1){ //如果桶中只有一个数则直接取出
A[c++] = t[i][0];
}else if(num[i] > 1){ //如果桶中不止一个数，则另存如数组B递归
int[] B = new int[num[i]];
for(int j = 0;j < num[i];j++){
B[j] = t[i][j];
sort(B,num[i]); //递归方法
}
}
}
return A;
}
public static void main(String[] args) {
RadixSort r = new RadixSort();
int[] A = {12,1,23,123,34};
r.sort(A, A.length);
for(int a : A){
System.out.println(a);
}
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/133297.html原文链接：https://javaforall.net
