一、什么是基数排序
基数排序（radix sort）属于“分配式排序”(distribution sort），又称“桶子法”(bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法基数排序(Radix Sort)是桶排序的扩展基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字，然后按每个位数分别比较。二、基数排序的思想 这里挂上b站上韩老师的视频讲解，十分感谢！！！
1、将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后， 从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完 成以后,数列就变成一个有序序列。
2、图解 ——(这里我偷个懒就无耻的截取视频中的步骤了，建议有时间的看视频！！！) 第一轮 第二轮 第三轮
三、实现需要基数排序需要考虑的点
1、根据上面的排序次数、怎么知道要排序多少次？ ———解答—— 数组中数值最大的元素是几位数的就排序几次 2、怎么根据排序的次数取出个位数、十位数、百位数字？ ——解答—— 一个公式 （当前元素/x）%10 x,第一次是1 ,第二次是10 每次排序结束就让x*10
四、代码实现(暂时是自己根据排序的思想写出来的，可能存在不足，日后会有更新、但排序正常)
public class RadixSort { public static void main(String[] args) { int[] array = new int[20]; for (int i = 0; i < array.length; i++) { array[i] = (int)(Math.random()*10000); } int[] ints = radixSort(array); System.out.println(Arrays.toString(ints)); } public static int[] radixSort(int[] array){ // 用一个二位数组来定义桶 int[10][array.length] // 10: 每个数字的取值区间是[0-9] // array.length 表示最坏情况下所有的数据都在一个桶内 int[][] bucket = new int[10][array.length]; // 如果往桶中存放数据、避免数据覆盖需要记录这个桶中已经了多少个数据 int[] bucketIndex = new int[10]; // 遍历数组得到最大值是多少位数的 int maxValuePosition = 1; int maxValue = array[0]; for (int i = 0; i < array.length; i++) { if (array[i]>=maxValue){ maxValue = array[i]; } } System.out.println("最大值="+maxValue); while (maxValue/10>0){ maxValuePosition++; maxValue /= 10; } System.out.println("位数:"+maxValuePosition); // 第一次是1 第二次为10 、规律是1*10n次方 n从0递增 int sortNumber = 1; // 用来记录第几次排序 int sort = 1; while ((maxValuePosition--) >= 0){ // 将数据放入桶中 for (int i = 0; i < array.length; i++) { // int kk = ((array[i]%10)/sortNumber); int digitNumber = (array[i]/sortNumber)%10; bucket[digitNumber] [bucketIndex[digitNumber]] = array[i]; bucketIndex[digitNumber] +=1 ; } // 打印数据 begin // System.out.println("桶数据如下"); // for (int i = 0; i < 10; i++) { // for (int j = 0; j < array.length; j++) { // System.out.print( bucket[i][j]+"\t"); // } // System.out.println(""); // } // System.out.println("桶下标记录如下"); // for (int i = 0; i < bucketIndex.length; i++) { // System.out.print(bucketIndex[i]+"\t"); // } // 打印数据 end // 从桶中取出数据 放入数组中 int j = 0; for (int i = 0; i < 10; i++) { int k = 0; while (bucketIndex[i]>0){ array[j++] = bucket[i][k++]; bucketIndex[i]--; } } // 打印信息 begin // System.out.println("第"+ sort++ +"次排序后"); // System.out.println(Arrays.toString(array)); // System.out.println("桶下标记录如下"); // for (int i = 0; i < bucketIndex.length; i++) { // System.out.print(bucketIndex[i]+"\t"); // } // 打印信息 end sortNumber *=10; } return array; } }五、个人总结 这种排序的时间复杂度 O(nlog( r)m) ，但创建桶需要耗费空间、10个桶不变、每个桶的大小是需要排序的数组的大小。
