参考: 基数排序

1. 简介

• 基数排序是一种非比较型整数排序算法，
• 其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
• 由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序的方式有两种

1. LSD（Least significant digital）
2. MSD（Most significant digital）

LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

下面我们以LSD举例

2. 实现

实现思路

1. 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
2. 然后，从最低位开始，依次进行一次排序。
3. 这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

Java实现

public class RadixSort {

    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    
    //获取最高位数
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    
    //自动扩容，并保存数据
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

3. 效率

复杂度

基数排序的时间复杂度是O(k*n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(nlogn)，k的大小取决于数字位的选择（比如比特位数），和待排序数据所属数据类型的全集的大小；k决定了进行多少轮处理，而n是每轮处理的操作数目。

• 时间复杂度: O(k*n)
• 空间复杂度: O(k+n)

使用前提

基数排序如果想效率比较高, 则对要排序的数据有要求

• 数据可以用位的用"位"来分割
• "位"之间有递进关系
• 每一位的数据范围不能太大，要可以用线性排序算法来排序

如果不能满足这几点, 基数排序就无法使用