1、基本思想
把待排序序列的数值统一为同样的数位长度，数位较短的数字在前面补零。然后从最低位开始，依此进行依此排序。这样从最低位排序一直到最高位排序完成后，数列就变成一个有序序列。
基数排序属于分配式排序，又称桶子法。
2、图解
假设存在10个桶，分别为0-9号桶。
假设待排序序列为：{64，8，216，512，27，729，000，001，343，125}
首先把数值统一为同样的长度：{064，008，216，512，027，729，000，001，343，125}
然后从最低位开始，依此进行依此排序。
第一轮，遍历序列，依次把数值放置到和个位数相同的编号的桶当中。
然后按照桶编号依次拿出数字：{000，001，512，343，064，125，216，027，008，729}
第二轮，遍历第一轮结束的序列，依次把数值放置到和十位数相同的编号的桶当中。
然后按照桶的编号依次拿出数字：{000，001，008，512，216，125，027，729，343，064}
第三轮，遍历第二轮结束的序列，依次把数值放置到和百位数相同的编号的桶当中。
然后按照桶的编号依次拿出数字：{000，001，008，027，064，125，216，343，512，729}。
最大数字对应字符串长度位3，所以执行3轮就排序好了。
3、代码实现
package cn.klb.datastructures.sort;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 实现数组的基数排序（桶子法）
* @Date: Create in 2023/4/5 15:06
* @Modified By:
*/
public class Radix {
public static void sort(int[] arr) {
// 找到待排序序列最大的数字
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 获取最大数字的对应字符串长度
int maxLength = ("" + max).length();
// 定义一个二维数组代表所有桶
// 比如：bucket[0] 表示0号桶
int[][] bucket = new int[10][arr.length];
// 定义一个一维数组保存每个桶元素的数量
// 比如：elementNums[2] == 3 表示2号桶有3个元素
int[] elementNums = new int[10];
// 桶的序号 0~9
int no = 0;
// 元素从桶里放回数组时用到
int index = 0;
// i == {0,1,2,...,maxLength} 分别表示个、十、百...
for (int i = 0; i < maxLength; i++) {
// arr数组每个元素放到指定的桶里
for (int j = 0; j < arr.length; j++) {
no = (int) (arr[j] / Math.pow(10, i) % 10);
bucket[no][elementNums[no]++] = arr[j];
}
// 每个桶里的元素按顺序覆盖回原数组
for (int k = 0; k < 10; k++) {
for (int count = 0; count < elementNums[k]; count++) {
arr[index++] = bucket[k][count];
}
elementNums[k] = 0; // 放好了存量就为0
}
// 执行完一轮后，执行清零操作
index = 0;
}
}
}
4、时间复杂度
代码中的基数排序不能排序负数，若要排序负数，得进行附加操作，但是原理是不变的。基数排序的一个应用是将字符串排序。
一般来说，在第k轮后，元素按第k低位有序，所以运行结束后所有元素就完全有序了。运行时间是O(p(n+b))，其中p是轮数，n是待排序元素个数，b是桶的个数。
5、稳定性
元素装入桶的顺序和从桶里倒出来的顺序是不变的，因此，相同元素的前后顺序不会发生改变，因此基数排序是稳定的。
6、测试
package cn.klb.test.datastructurestest;
import cn.klb.datastructures.sort.*;
import org.junit.Test;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author DDKK.COM 弟弟快看，程序员编程资料站
* @Description: 排序测试
* @Date: Create in 2023/4/3 21:32
* @Modified By:
*/
public class SotrTest {
@Test
public void testRadix(){
int[] arr = new int[8000000];
for (int i = 0; i < 8000000; i++) {
arr[i] = (int) (Math.random() * 80000000);
}
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
Date date1 = new Date();
System.out.println("-----" + sdf.format(date1) + "-----");
//System.out.println(Arrays.toString(arr));
Radix.sort(arr);
Date date2 = new Date();
System.out.println("-----" + sdf.format(date2) + "-----");
//System.out.println(Arrays.toString(arr));
// 800万的随机数据进行基数排序，我的电脑花了大约2秒（测不了8000万，内存炸了）
}
}