基数排序 是将整数按位数切割成不同的数字，然后按每个位数分别比较从而得到有序的序列。
本文以数组中元素均为正整数来演示。
给定一个数组 arr = [ 53, 3, 542, 748, 14, 214 ];
准备十个桶：0~9
第一轮按照元素的个位数排序
0~9的各个桶内分别存放数组中各元素的个位数，按照数组元素的顺序依次存放
53个位数为 3 ->放入第3个桶（桶下标为3）
3个位数为 3 ->放入第3个桶（桶下标为3）
542个位数为 2 ->放入第2个桶（桶下标为2）
748个位数为 8 ->放入第8个桶（桶下标为8）
14个位数为 4 ->放入第4个桶（桶下标为4）
214个位数为 4 ->放入第4个桶（桶下标为4）
按照桶的顺序：从左向右，按照桶中元素存放的顺序：从上到下 依次取出元素，组成新的数组。
542,53,3,14,214,748
第二轮按照元素的十位数排序
0~9的各个桶内分别存放数组中各元素的十位数，按照数组元素的顺序依次存放
53十位数为 5 ->放入第5个桶（桶下标为5）
3十位数为 0 ->放入第0个桶（桶下标为0）
542十位数为 4 ->放入第4个桶（桶下标为4）
748十位数为 4 ->放入第4个桶（桶下标为4）
14十位数为 1 ->放入第1个桶（桶下标为1）
214十位数为 1 ->放入第1个桶（桶下标为1）
按照桶的顺序：从左向右，按照桶中元素存放的顺序：从上到下 依次取出元素，组成新的数组。
3,14,214,542,748,53
第三轮按照元素的百位数排序
0~9的各个桶内分别存放数组中各元素的百位数，按照数组元素的顺序依次存放
53百位数为 0 ->放入第0个桶（桶下标为0）
3百位数为 0 ->放入第0个桶（桶下标为0）
542百位数为 5 ->放入第5个桶（桶下标为5）
748百位数为 7 ->放入第7个桶（桶下标为7）
14百位数为 0 ->放入第0个桶（桶下标为0）
214百位数为 2 ->放入第2个桶（桶下标为2）
按照桶的顺序：从左向右，按照桶中元素存放的顺序：从上到下 依次取出元素，组成新的数组。
3,14,53,214,542,748
从上述步骤可以看出
1、排序的总轮数为，数组中最大元素的长度
2、需要使用二维数组，存储各元素在各桶中的位置。即：arr[第几个桶][桶中第几个位置]
实现说明：
1、获取数中最大的元素
2、获取最大元素的长度maxLength
3、定义一个二维数组存储各元素在对应桶中的具体位置，例如第一轮排序时，第2个桶中第1个元素为542，第4个桶中第2个元素为214
4、定义一个一维数组长度为10，用于存储各个桶中元素的个数，例如第一轮排序时，第3个桶中有2个元素，第8个桶中有一个元素
5、外层for循环，使用maxLength控制循环次数，同时，每次循环取的是不同位数上的元素，所以需要定义变量n=1且n在每一轮循环结束后要*10
6、内层for循环，根据需要排序的数组arr的长度，控制循环次数
1）每一次遍历arr数组时，需要根据公式算出当前轮需要获取的元素对应位数的数
2）然后，将该元素存入二维数组中，其中二维数组的横坐标即为获取到的对应元素位上的数，纵坐标即为一维数组下标为对应元素位上的数的值
3）因为可能有多个元素的对应位上的数相同，所以一维数组下标要后移，这样不断的累加，最后就可以统计出各个桶中有几个元素
7、每次内层循环结束，即一轮排序结束，需要按照桶的顺序，从左向右，按照桶中元素存放的顺序：从上到下 依次取出元素，组成新的数组
1）因为一维数组中，分别存储的是各个桶中元素的个数，通过for循环遍历一维数组
2）当一维数组中元素的值为0，就代表对应桶中没有元素
3）当一维数组中的元素的值不为0时，使用for循环遍历对应桶中的元素，并存入arr中
4）每轮组成新的数组后，将各桶中的元素个数置为0
代码实现：
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int arr[] = {53, 3, 542, 748, 14, 214};
radixSort(arr);
}
public static void radixSort(int[] arr) {
//得到数组中最大的数的位数
int maxNum = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxNum) {
maxNum = arr[i];
}
}
//得到最大数是几位数
int maxLength = (maxNum + "").length();
//定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
int[][] bucket = new int[10][arr.length];
//每个桶存入了几个数字
int[] everyBucketNum = new int[10];
// n* = 10 的原因是
//123取出个位数字是 123 % 10，即 123 / 1 %10
//123 取出十位数字是123 / 10 % 10;
//123 去除百位数字是123 /100 % 10
//以此类推
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//取出每个元素的对应位的值
int digit = arr[j] / n % 10;
//放入到对应的桶中
bucket[digit][everyBucketNum[digit]] = arr[j];
everyBucketNum[digit]++;
}
//按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
int index = 0;
//遍历每一桶，并将桶中是数据，放入到原数组
for (int k = 0; k < everyBucketNum.length; k++) {
if (everyBucketNum[k] != 0) {
for (int l = 0; l < everyBucketNum[k]; l++) {
arr[index++] = bucket[k][l];
}
}
//放回原数组后，需要将每个 everyBucketNum[k] = 0
everyBucketNum[k] = 0;
}
System.out.println("第" + (i + 1) + "轮，对个位的排序处理 arr =" + Arrays.toString(arr));
}
}
}
输出结果：
第1轮，对个位的排序处理 arr =[542, 53, 3, 14, 214, 748]
第2轮，对个位的排序处理 arr =[3, 14, 214, 542, 748, 53]
第3轮，对个位的排序处理 arr =[3, 14, 53, 214, 542, 748]