【排序算法】7.基数排序

基数排序（RadixSort）是桶排序的升级版，属于分配式排序。它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。

具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序示意图

在这个过程中创建桶进行辅助排序

桶

特点

速度快
空间换时间，排序速度快

空间浪费巨大
因为排序基于桶，桶需要占据大量空间，一个长度为 length 的数组，它的桶就是一个 [10][length] 的二维数组（如果算上负数，那就需要 [19][length] 的二维数组）

不适合负数排序
因为桶是二维数组，第一维度代表的是每一位的数值，如果有负数会报错（如： new int[-10]），需要进行改造

java 实现：

public class RadixSortTest {
    public static void main(String[] args) {
        int[] input = {2,5,4,89,20,89,6,0,54,78,2};
        radixSort(input);
        PrintUtils.print(input);
    }

    public static void radixSort(int[] arr) {
        //桶
        int[][] bucket = new int[10][arr.length];
        //统计每个桶的有效元素个数
        int[] bucketCounter = new int[10];
        //位数
        int place = 0;
        int max = 0;
        for (int n = 0; n < arr.length; n++){
            if (arr[n] > max){
                max = arr[n];
            }
        }
        int maxLength = (max + "").length();
        for (int m = 0; m < maxLength; m++){
            //按位数，依次存入对应的桶中
            for (int i = 0; i < arr.length; i++){
                int placeValue = arr[i] / (int)Math.pow(10, place) % 10;
                bucket[placeValue][bucketCounter[placeValue]++] = arr[i];
            }
            place++;

            //从桶中取出，依次放回 arr
            int returnPointer = 0;
            for (int j = 0; j < 10; j++){
                int[] placeArr = bucket[j];
                for (int k = 0; k < bucketCounter[j]; k++){
                    arr[returnPointer++] = placeArr[k];
                }
                //还原 bucketCounter
                bucketCounter[j] = 0;
            }
        }
    }
}

时间复杂度

• 最优时间复杂度：O(d(n+r))
• 最坏时间复杂度：O(d(n+r))
• 稳定性：稳定