思路
基数排序也是三个桶排序算法之一，排序过程也是不需要进行比较。
基数排序的主要思路是：
1、先按个位数不同，把数组中所有元素放到0~9这10个不同的桶中；
2、从桶中按先入先出的顺序取出数据，此时数组个位数已经有序，再按照十位，放入桶中；
3、再取出，直到所有位数到进过桶，就完成了整个数组的排序。
另外说明一下计数排序的适用场景：
1、因为是按位数进行排序的，所以只能排正整数；
2、数组中的元素间隔越小越好。比如如果有一个数组是[1, 2, 111111111]，这样虽然只有一个数有9位，但是所有数都要跟着入桶。
讲解
有数组如下：
image.png
我们先按各位给所有数字入桶，入桶后如下：
image.png
第一次按个位数入桶后，从桶中把数取出得到如下数组：
image.png
然后按照十位数进行第二次入桶：
image.png
再次取出，得到数组如下：
image.png
下面进行百位数的最后一次入桶操作：
image.png
最后取出，排序完成：
image.png
实现
@Test
public void sortTest() {
int[] nums = new int[]{2, 0, 31, 248, 243, 36, 46, 55};
radixSort(nums);
System.out.println(Arrays.toString(nums));
}
private void radixSort(int[] nums) {
if (nums.length < 2) {
return;
}
// 找到最大值，确定需要入几次桶
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
}
}
// 遍历入桶和取出，次数为最大数的位数
for (int i = 0, divideNum = 10; i < String.valueOf(maxValue).length(); i++, divideNum *= 10) {
// 初始化10个桶
int[][] bucketArray = new int[10][0];
// 遍历数组元素，按当前的数位入桶
for (int j = 0; j < nums.length; j++) {
int remainder = nums[j] % divideNum;
if (divideNum > 10) {
remainder = remainder / (divideNum / 10);
}
bucketArray[remainder] = arrayAppend(bucketArray[remainder], nums[j]);
}
// 从桶中取出数据并放回数组
for (int j = 0, l = 0; j < 10; j++) {
for (int k = 0; k < bucketArray[j].length; k++) {
nums[l++] = bucketArray[j][k];
}
}
}
}
private int[] arrayAppend(int[] array, int num) {
int[] ints = Arrays.copyOf(array, array.length + 1);
ints[ints.length - 1] = num;
return ints;
}
看下运行结果：
image.png
