目录
一、概念了解
二、原理分析
三、算法实现
四、测试结果
一、概念了解
LSD法：最低位优先(Least Significant Digit first)法，先从最低位开始排序，再对次低位进行排序，依次重复，直到对最高位排序后便得到一个有序序列。
最低位：对于一个整数而言，最低位就是个位数，如123的最低位就是3。
基数排序(radix sort)：属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort)或bin sort。
基数排序原理：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
二、原理分析
原理见下图
三、算法实现
1、基数排序算法，这是带注释的代码，可以根据这些注释进一步了解基数排序算法每一步的含义，如果不需要可以下拉，有完整且直接可运行的代码。
public void radixSort(int[] arrays) {
//取最大值的位数
int max = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] > max) {
max = arrays[i];
}
}
//将最大数先转换为字符串，再求其长度（位数）
int len = (max + "").length();
//System.out.println(len);
//System.out.println("-------------------------");
//定义一个二维数组，【0-9】× arrays数组的长度(假如无序数列中的所有十位数都是1，最多也就达到arrays的长度)
int[][] arrs = new int[10][arrays.length];
//定义一个辅助一维数组，存储二维数组元素信息，其下标包括【0-9】
int[] array = new int[10];
//最大值位数为3，循环3次
//循环次数
int n = 0;
//由元素位数计算出的下标（对应到二维数组的行）
int rowindex = 0;
int k = 0;
while (n < len) {
//计算无序数列arrays中每一个元素的十位数
for (int i = 0; i < arrays.length; i++) {
//以下为数学公式，Math.pow(10,n)返回类型为double，因此计算后结果也为double，需要强转为int类型
rowindex = (int) (arrays[i] / Math.pow(10, n) % 10);
//System.out.print(index + "t");//循环输出个位、十位、百位……上的数
//按下标将arrays中的元素依次放入二维数组arrs中
//array[rowindex]中存放二维数组每一列中存放元素的个数，因为每一列的元素依次向下存放，所以需要知道列下标。
arrs[rowindex][array[rowindex]] = arrays[i];
//二维数组的列下标，放进一个下标就+1，由辅助数组array帮助计算二维数组的列放到了第几个。
array[rowindex]++;
}
//依次取出二维数组中的元素
for (int i = 0; i < arrays.length; i++) {
//如果辅助数组中的值不为0，说明对应的列中有元素
if (array[i] != 0) {
//元素的个数即为辅助数组存储的数
for (int j = 0; j < array[i]; j++) {
arrays[k] = arrs[i][j];
//System.out.print(randomArrays[k] + "t");//每一次输出的数列
k++;
}
//使一维数组中的值全部为0，为下一次循环做准备
array[i] = 0;
}
}
//System.out.println();
//下一次循环要从0开始
k = 0;
//控制while循环的次数
n++;
}
}
2、完整代码，包括RadixSort02 类和Test测试类
RadixSort02 类
public class RadixSort02 {
public int maxlen(int[] arrays) {
int max = 0;
for (int i = 0; i < arrays.length; i++) {
if (max < arrays[i]) {
max = arrays[i];
}
}
return (max + "").length();
}
public void sort(int[] arrays, int len) {
//二维数组，存放元素
int[][] arrs = new int[10][arrays.length];
//一维数组，存放二维数组信息
int[] arr = new int[10];
//循环计数
int count = 0;
//记录二维数组列下标
int index = 0;
//辅助计算下标
int n = 1;
//辅助取值
int k = 0;
while (count < len) {
//根据位数放元素
for (int i = 0; i < arrays.length; i++) {
index = arrays[i] / n % 10;
arrs[index][arr[index]] = arrays[i];
arr[index]++;
}
//取出元素赋值给arrays，为了下一轮比较
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
for (int j = 0; j < arr[i]; j++) {
arrays[k] = arrs[i][j];
k++;
}
arr[i] = 0;
}
}
count++;
n *= 10;
k = 0;
}
}
}
测试类
import java.util.Arrays;
public class Test02 {
public static void main(String[] args) {
RadixSort02 sort02 = new RadixSort02();
int[] arrays = new int[]{2, 5, 34, 23, 789, 33, 1, 4526, 678};
int len = sort02.maxlen(arrays);
sort02.sort(arrays, len);
//可循环输出排序好的数组
for (int i = 0; i < arrays.length; i++) {
System.out.print(arrays[i] + "t");
}
System.out.println();
System.out.println("-----------------");
//使用Arrays的toString()方法输出
System.out.println(Arrays.toString(arrays));
}
}
四、测试结果
小句分享：
历史表明，任何服务的用户达数百万时，被颠覆的命运就不可避免。大公司要求企业家将利益放在平衡各方利益上，这就为创业者敞开了大门，创业者进来获得那些公司服务不到的客户。
历史表明，任何服务的用户达数百万时，被颠覆的命运就不可避免。大公司要求企业家将利益放在平衡各方利益上，这就为创业者敞开了大门，创业者进来获得那些公司服务不到的客户。
以上仅供学习参考，可能会有不正确的地方，不过问题应该不大吧，注释是我的想法，表述可能有一点点粗糙，希望可以帮助大家！
