基数排序Radix Sort
1. Radix Sort介绍
Radix Sort属于“分配式排序”（Distribution Sort），又称“桶子法”（Bucket Sort），其是通过比较待排序序列的所有元素的各个位的值，将元素分配至“桶”中，以达到排序的目的。Radix Sort是一种效率较高且稳定的排序算法，其是桶排序的扩展。
Radix Sort的基本思想是：将待排序序列中所有数值统一为同样的数位长度，数位较短的在前面补零。然后从最低位开始，依次将其放入对应的“桶”中，然后按序取出放回原数组，并进行下一轮针对下一个数位的同样操作。这样从最低位一直到最高位排序完成后，就得到了一个有序序列。
注意：Radix Sort是典型的空间换时间的方法，占用内存很大，当面对海量数据排序时，容易造成OutOfMemoryError。
2. 图解说明Radix Sort的步骤
举一个例子来具体说明Radix Sort的过程。给出一个无序数列：23，1，4，9，98，132，42使用基数排序将其排列成一个从小到大的有序数列。
- 确定待排序序列中最大的元素有几位，即确定Radix Sort执行的轮数rounds；
- 定义10个“桶”（0-9），可以用二维数组bucket [10] [nums.length]来表示。取每一个元素的个位的值（nums[i] / 1 % 10），并将元素分别装入对应下标的桶中。同时定义一个一维数组bucketElementCounts [10]用于记录每个桶中实际放入元素的个数；
- 将桶中的元素按下标顺序依次取出，放入到原来的序列中，每取完一个桶中的元素，就将该桶对应的bucketElementCounts置为0，便于下一次重新开始计数；
- 执行下一轮针对十位数字的操作，取每一个元素的十位的值（nums[i] / 10 % 10），分别装入对应下标的桶中；
- 重复上面的步骤直至达到rounds轮结束，此时序列排序完成。
3. 代码实现
package com.algorithm;
import java.util.Arrays;
/**
* @author SnkrGao
* @create 2023-04-18 15:52
*/
public class RadixSort {
public static void main(String[] args) {
int[] nums = {23,1,4,9,98,132,42};
System.out.println("排序前的数组为：");
System.out.println(Arrays.toString(nums));
System.out.println("---------------------------------");
radixSort(nums);
System.out.println("---------------------------------");
System.out.println("排序后的数组为：");
System.out.println(Arrays.toString(nums));
}
public static void radixSort(int[] nums) {
int rounds = getRounds(nums); // 执行轮数
int bucket[][] = new int[10][nums.length]; // 定义二维数组表示十个桶
int bucketElementCounts[] = new int[10]; // 定义一个一维数组表示每个桶中实际放入的元素个数
// 最外层循环i表示排序的轮次，n用于取出元素的个位/十位/百位，每一轮结束后n *= 10
for (int i = 0, n = 1; i < rounds; i++, n *= 10) {
// 遍历每一个元素
for (int j = 0; j < nums.length; j++) {
// 计算元素的某个数位的值（n=1为个位，n=10为十位，n=100为百位）
int digitOfElement = nums[j] / n % 10;
// 将元素放入对应的桶中，每放一个元素该桶的元素计数 + 1，初始时每个桶的bucketElementCounts均为0
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = nums[j];
bucketElementCounts[digitOfElement]++;
}
// 表示从桶中取出的元素放入原nums的位置
int index = 0;
// 遍历每一个桶
for (int j = 0; j < bucket.length; j++) {
// 从桶中按下标顺序依次取出元素
for (int k = 0; k < bucketElementCounts[j]; k++) {
// 将元素放入原nums数组中
nums[index++] = bucket[j][k];
}
// 注意：每取完一个桶都将该桶存放的元素个数置零，以便下一轮放入桶中时重新计数
bucketElementCounts[j] = 0;
}
System.out.println("第" + (i + 1) + "轮的排序结果为：");
System.out.println(Arrays.toString(nums));
}
}
// 计算nums中最大元素的位数，即排序执行的轮数
public static int getRounds(int[] nums) {
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
return (max + "").length();
}
}