基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述

• 取得数组中的最大数，并取得位数

• arr为原始数组，从最低位开始取每个位组成radix数组

• 对radix进行计数排序（利用计数排序适用于小范围数的特点）

动图演示

代码实现

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    radixSort(array);

    System.out.println(Arrays.toString(array));
}

public static void radixSort(int[] array) {
    int length = array.length;
    // 找最大值
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    for (int divider = 1; divider <= max; divider *= 10) {
        // 数字个位、百位、千位都是 0~9 的数字，所以这里数组长度固定写 10
        int[] counts = new int[10];
        // 统计出现次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] / divider % 10]++;
        }
        // 累加次数
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i-1];
        }

        // 创建和 array 相同大小有序数组，把array中的数据放到有序数组中合适的位置上
        int[] newArray = new int[length];
        for (int i = length-1; i >= 0; i--) {
            // 填充一个数据后，把累加次数自减，以便相同的数据可以填到下一个空位
            newArray[--counts[array[i] / divider % 10]] = array[i];
        }
        // 数据回写
        for (int i = 0; i < length; i++) {
            array[i] = newArray[i];
        }
    }
}

算法分析

最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)

基数排序有两种方法：

MSD 从高位开始进行排序 LSD 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶

• 计数排序：每个桶只存储单一键值

• 桶排序：每个桶存储一定范围的数值