Nice！第一次见这么全面的Java实现八大排序算法，爱了( 六 ) 它们都属于内部排序

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital）从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。 MSD方式适用于位数多的序列 。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。 LSD方式适用于位数少的序列 。

文章插图
算法描述我们以LSD为例，从最低位开始，具体算法描述如下：

取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；

代码实现基数排序：通过序列中各个元素的值，对排序的N个元素进行若干趟的“分配”与“收集”来实现排序。

分配：我们将L[i]中的元素取出，首先确定其个位上的数字，根据该数字分配到与之序号相同的桶中
收集：当序列中所有的元素都分配到对应的桶中，再按照顺序依次将桶中的元素收集形成新的一个待排序列L[] 。对新形成的序列L[]重复执行分配和收集元素中的十位、百位...直到分配完该序列中的最高位，则排序结束

public static void sort(int[] arr) {if (arr.length <= 1) return;//取得数组中的最大数 ， 并取得位数int max = 0;for (int i = 0; i < arr.length; i++) {if (max < arr[i]) {max = arr[i];}}int maxDigit = 1;while (max / 10 > 0) {maxDigit++;max = max / 10;}//申请一个桶空间int[][] buckets = new int[10][arr.length];int base = 10;//从低位到高位 ， 对每一位遍历 ， 将所有元素分配到桶中for (int i = 0; i < maxDigit; i++) {int[] bktLen = new int[10];//存储各个桶中存储元素的数量//分配：将所有元素分配到桶中for (int j = 0; j < arr.length; j++) {int whichBucket = (arr[j] % base) / (base / 10);buckets[whichBucket][bktLen[whichBucket]] = arr[j];bktLen[whichBucket]++;}//收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞int k = 0;for (int b = 0; b < buckets.length; b++) {for (int p = 0; p < bktLen[b]; p++) {arr[k++] = buckets[b][p];}}System.out.println("Sorting: " + Arrays.toString(arr));base *= 10;}}

复杂度分析以下是基数排序算法复杂度，其中k为最大数的位数：

文章插图
其中， d 为位数， r 为基数， n 为原数组个数。在基数排序中，因为没有比较操作，所以在复杂上，最好的情况与最坏的情况在时间上是一致的，均为 O(d*(n + r)) 。
总结和思考基数排序更适合用于对时间, 字符串等这些整体权值未知的数据进行排序。
基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

八大排序算法总结各种排序性能对比如下:

文章插图
从时间复杂度来说：

平方阶O(n2)排序：各类简单排序：直接插入、直接选择和冒泡排序
线性对数阶O(nlog?n)排序：快速排序、堆排序和归并排序
O(n1+§))排序， §是介于0和1之间的常数：希尔排序
线性阶O(n)排序：基数排序，此外还有桶、箱排序

论是否有序的影响：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将转化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

文章插图