一. 基数排序的描述
原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
- MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
- LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序
二. 实现思路
① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
② 从最低位开始，依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
排序的次数取决于最大数的位数
三. 代码
package c06Sort;import java.util.Arrays;
//基数（堆）
public class c07RadixSort {public static void main(String[] args) {int [] arr = {53,3,524,748,14,214};Radix(arr);} public static void Radix(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] ;//例如bucketElementCounts[4]=3 表示第五个桶 有三个数据（下表为0开始）for (int i = 0, n = 1; i < maxlength; i++, n = n * 10) {// 根据位数进行分桶for (int j = 0; j < arr.length; j++) {// 给所有的数分桶int digitOfElement = arr[j] / n % 10; // 定义个位数的 数字 他就对应桶的位置// 放入相应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];// bucketElementCounts[digitOfElement] 以digitOfElement的数据有几个元素bucketElementCounts[digitOfElement]++; // 使用过后加一}// 按照桶的顺序 按顺序取出元素放入原数组int index = 0;// 遍历每一个桶 固定的十个桶for (int k = 0; k < 10; k++) {// 如果桶里面有元素if (bucketElementCounts[k] != 0) {// 循环第k 个数组 取出里面的数据for (int l = 0; l < bucketElementCounts[k]; l++) {arr[index] = bucket[k][l];index++;}}// 每个桶数据输出之后 重新置为0；bucketElementCounts[k] = 0;}System.out.println("第"+(i+1)+"轮" + Arrays.toString(arr));}}}
四. 结果
