为了方便大家理解，这里我并没有使用循环处理，而是详细写出了每一轮的步骤，代码注释也很详细。
接下来编写测试代码：
public static void main(String[] args) {
int[] arr = { 53, 3, 542, 748, 14, 214 };
raixSort(arr);
}
运行结果：
第一轮:[542, 53, 3, 14, 214, 748]
第二轮:[3, 14, 214, 542, 748, 53]
第三轮:[3, 14, 53, 214, 542, 748]
如果你能够看懂上面的代码，那么接下来就是整合了，通过循环对上面的代码进行优化。
代码如下：
public static void raixSort(int[] arr) {
// 得到数组中最大的数
int max = arr[0];// 假设第一个数就是数组中的最大数
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 得到最大数是几位数
// 通过拼接一个空串将其变为字符串进而求得字符串的长度，即为位数
int maxLength = (max + "").length();
// 定义一个二维数组，模拟桶，每个桶就是一个一维数组
// 为了防止放入数据的时候桶溢出，我们应该尽量将桶的容量设置得大一些
int[][] bucket = new int[10][arr.length];
// 记录每个桶中实际存放的元素个数
// 定义一个一维数组来记录每个桶中每次放入的元素个数
int[] bucketElementCounts = new int[10];
// 通过变量n帮助取出元素位数上的数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// 针对每个元素的位数进行处理
int digitOfElement = arr[j] / n % 10;
// 将元素放入对应的桶中
// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
// 将桶中的元素个数++
// 这样接下来的元素就可以排在前面的元素后面
bucketElementCounts[digitOfElement]++;
}
// 按照桶的顺序取出数据并放回原数组
int index = 0;
for (int k = 0; k < bucket.length; k++) {
// 如果桶中有数据，才取出放回原数组
if (bucketElementCounts[k] != 0) {
// 说明桶中有数据，对该桶进行遍历
for (int l = 0; l < bucketElementCounts[k]; l++) {
// 取出元素放回原数组
arr[index++] = bucket[k][l];
}
}
// 每轮处理后，需要将每个bucketElementCounts[k]置0
bucketElementCounts[k] = 0;
}
}
}
测试代码：
public static void main(String[] args) {
int[] arr = { 53, 3, 542, 748, 14, 214 };
raixSort(arr);
System.out.println(Arrays.toString(arr));
}
运行结果：
[3, 14, 53, 214, 542, 748]
这样，基数排序就完成了。大家不要看到代码很多就怕了、烦了，觉得好难，其实也不能说一点难度都没有吧，只是要去理解这个过程，所以对于排序过程的分析我写了很多，也是为了能让你们更加理解，掌握了过程之后，相信理解这些代码也不是难事了。
其它：
这里说一说基数排序的一些其它内容，为什么单独只说基数排序呢？我们在前面提到了，基数排序是用空间换时间的经典算法，所以基数排序对于元素排序是非常快的。不信我们可以测试一下(先测试八十万个数据的排序时间)：
public static void main(String[] args) {
int[] arr = new int[800000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
Date date = new Date();
SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
String dateStr = format.format(date);
System.out.println("排序前的时间是:" + dateStr);
raixSort(arr);
Date date2 = new Date();
String dateStr2 = format.format(date2);
System.out.println("排序前的时间是:" + dateStr2);
}
运行结果：
排序前的时间是:17:37:21
排序前的时间是:17:37:21
一秒钟时间不到就完成排序了。
我们再测试一下八百万个数据的排序：
public static void main(String[] args) {
int[] arr = new int[8000000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
Date date = new Date();
SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
String dateStr = format.format(date);
System.out.println("排序前的时间是:" + dateStr);
raixSort(arr);
Date date2 = new Date();
String dateStr2 = format.format(date2);
System.out.println("排序前的时间是:" + dateStr2);
}
运行结果：
排序前的时间是:17:38:04
排序前的时间是:17:38:05
