算法思想：
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，
它是透过键值的各个位的值，将要排序的元素分配至某些“桶”中，藉以达到排序的作用， 属于稳定性排序
理解：
初始10个桶对应标号 0-9，
第一次将每个元素按照个位放入对应下标的桶中;
将按照个位拍好序列的元素依次放入arr中（此时个位排好序了，而且如果只有1位，从0-9的这些数已经是有序序列了）
在新的arr中，第二次将每个元素的十位放入对应下标的桶中; (在个位已经拍好序的基础上，对十位也排好序)
（只有两位的话：如果十位不同，则放入不同的桶，直接能排好序了;如果十位相同，而个位是已经排好序的，也能对任何的两位数排好序）
依次类推。。。
public class RadixSorting {
public static void radixSort(int[] arr){
// 找出arr中最大的元素
int maxElement = getMaxElement(arr);
// 获取maxElement的length
int lenthForMaxElement = getMaxElementLen(maxElement);
//二维数组表示10个桶，每个桶用一维数组表示
int[][] buckets = new int[10][arr.length];
//用来记录每个桶所放元素的个数. 比如：bucketElementsCounts[0],记录的就是buckets[0]桶的放入数据的个数
int[] bucketElementsCount = new int[10];
for (int i = 0,n = 1; i < lenthForMaxElement; i++,n*=10) {
//比如：num = 10,按照个位放入对应下标的桶中；num = 100，按照十位放入对应下标的桶中
for (int j = 0; j < arr.length; j++) {
//取出个位/十位/百位....
int remainder = arr[j]/n % 10;
//arr[j]放入桶中
buckets[remainder][bucketElementsCount[remainder]] = arr[j];
//元素个数+1
bucketElementsCount[remainder]++;
}
//一轮放完后，按照桶的顺序（一维数组的下标依次取出数据放入原数组）
int index = 0;
//遍历每一个桶，并将桶中的数据放入原数组
for (int k = 0; k < bucketElementsCount.length; k++) {
//桶中有数据才放入数组
if (bucketElementsCount[k] != 0) {
for (int l = 0; l < bucketElementsCount[k]; l++) {
arr[index] = buckets[k][l];
index++;
}
}
//每一轮处理后都需要将 bucketElementsCount[k] = 0,用于下一轮桶中数据被覆盖！！！
bucketElementsCount[k] = 0;
}
}
}
public static void main(String[] args) {
int[] arr = {101,34,39,1,305,1,90,123};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
private static int getMaxElement(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
private static int getMaxElementLen(int maxElement) {
int temp = maxElement;
int counter=0;
while (temp >0) {
temp /=10;
counter++;
}
return counter;
}
}
用于辅助理解 - 第一轮排序
用于辅助理解 - 第二轮排序
