搜 索

排序算法丨基数排序

  • 218阅读
  • 2021年08月22日
  • 0评论
首页 / 默认分类 / 正文

前言

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

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

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

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

排序思路

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

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

  1. MSD(Most Significant Digit first):从最左侧高位开始进行排序。适用于位数多的序列。
  2. 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
打 赏
  • 支付宝
  • 微信
Alipay
WeChatPay
评论区
暂无评论
avatar