排序算法丨基数排序

前言

面对“排序10万个手机号码”、“排序字典中的英语单词”这些场景，快速排序可以做到 O(nlogn)，但还不够高效。
计数排序、桶排序能派上用场吗？手机号码有 11位，范围太大，显然不适合用这两种排序算法；英语单词不是整数，无法使用。

要比较两个手机号码 a，b的大小，如果在前面几位中，手机号码 a已经比手机号码 b大了，那后面的几位就不需要比较了。
借助稳定排序算法，可以先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11次排序之后，手机号码就都有序了。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。

像这样把字符串元素按位拆分，每一位进行一次计数排序的算法，就是基数排序。

基数排序(Radix Sort)，它的发明可以追溯到 1887年赫尔曼·何乐礼在打孔卡片制表机上的贡献：排序器每次只能看到一个列。
它是基于元素值的每个位上的字符来排序的，对于数字而言就是分别基于个位、十位、百位、千位等等数字来排序。

排序思路

将所有待比较数值统一为同样的数位长度，例如：长短不一的英语单词。
以最长的字符串为准，数位较短的数后面补“0”，因为根据 ASCII值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序，这样就可以继续用基数排序了。
然后从最低位开始依次进行一次排序，从最低位排序一直到最高位完成以后，数列就变成一个有序数列。

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

MSD(Most Significant Digit first)：从最左侧高位开始进行排序。适用于位数多的序列。
LSD(Least Significant Digit first)：从最右侧低位开始进行排序。适用于位数少的序列。

代码实现

public class RadixSort {
    /**
     * 得到数组前 n 位的最大值
     */
    private static int getMax(int[] arr, int n) {
        int mx = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > mx) {
                mx = arr[i];
            }
        }
        return mx;
    }

    private static void countSort(int[] arr, int n, int exp) {
        // 结果输出数组
        int[] output = new int[n];
        int i;
        // 创建辅助排序的统计数组，因为是统计数字，对应0-9
        int[] count = new int[10];
        // 填充
        Arrays.fill(count, 0);
        // 并把待排序的字符对号入座
        for (i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        // 统计数组做变形，后面的元素等于前面的元素之和
        for (i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        // 倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
        for (i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        // 下一轮排序需要以上一轮的排序结果为基础，因此把结果复制给 arr
        for (i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }
    // 基数排序
    private static void radixsort(int[] arr, int n) {
        // m 就是数组中最长字符串元素，即最大值元素
        int m = getMax(arr, n);
        // exp 10进制，从个位到高位
        for (int exp = 1; m / exp > 0; exp *= 10) {
            countSort(arr, n, exp);
        }
    }
    // 排序后输出
    static void print(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        int n = arr.length;
        radixsort(arr, n);
        print(arr, n);
    }
}

public class RadixSort2 {
    // ascii码的取值范围
    public static final int ASCII_RANGE = 128;

    public static String[] radixSort(String[] array, int maxLength) {
        // 排序结果数组，用于存储每一次按位排序的临时结果
        String[] sortedArray = new String[array.length];
        // 从个位开始比较，一直比较到最高位
        for (int k = maxLength - 1; k >= 0; k--) {
            // 计数排序的过程，分成三步：
            // 1.创建辅助排序的统计数组，并把待排序的字符对号入座，
            // 这里为了代码简洁，直接使用 ascii码范围作为数组长度
            int[] count = new int[ASCII_RANGE];
            for (int i = 0; i < array.length; i++) {
                int index = getCharIndex(array[i], k);
                count[index]++;
            }
            // 2.统计数组做变形，后面的元素等于前面的元素之和
            for (int i = 1; i < count.length; i++) {
                count[i] = count[i] + count[i - 1];
            }
            // 3.倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
            for (int i = array.length - 1; i >= 0; i--) {
                int index = getCharIndex(array[i], k);
                int sortedIndex = count[index] - 1;
                sortedArray[sortedIndex] = array[i];
                count[index]--;
            }
            // 下一轮排序需要以上一轮的排序结果为基础，因此把结果复制给array
            array = sortedArray.clone();
        }

        return array;
    }

    // 获取字符串第k位字符所对应的ascii码序号
    private static int getCharIndex(String str, int k) {
        // 如果字符串长度小于k，直接返回0，相当于给不存在的位置补0
        if (str.length() < k + 1) {
            return 0;
        }
        return str.charAt(k);
    }

    public static void main(String[] args) {
        String[] array = {"wdnmd", "abc", "qwe", "hhhhhh", "nobb", "lbwnb", "chinayyds"};
        System.out.println(Arrays.toString(radixSort(array, 3)));
    }
}

动画演示

演示动画来自于VisuAlgo

复杂度分析

根据每一位来排序，可以使用桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。
如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k * n)。当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。

基数排序的空间复杂度为 O(n + m)，m 是字符的取值范围大小。

基数排序不改变相同元素之间的相对顺序，因此它是稳定的排序算法。

适用场景

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a数据的高位比 b数据大，那剩下的低位就不用比较了。
除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n)了。

它更适合用于对时间、字符串等这些整体权值未知的数据进行排序。

参考

程序员小灰
 菜鸟教程
 Github-TheAlgorithms