排序算法 - 基数排序详解

编程知识更新时间:2023-05-02 12:09:58

基本介绍

基数排序(radix sort)的思想是多关键字排序，属于分配式排序。它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，然后依次收集各个桶内数据，通过分配和收集达到排序的目的。

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序示意图:

执行流程

下面通过一个例子来体会基数排序过程。

原始序列：80, 43, 155, 987, 100, 31, 6, 299, 155, 0

0）初始桶

每个关键字的每一位都是由“数字”组成的，数字的范围是0~9，所以准备10个桶用来放关键字。
要注意的是，组成关键字的每一位不一定是数字。如果关键字有一位是英文字母那么按这一位排序时，就要准备26个桶(假设不区分大小写)。这里所说的“桶”，其实是一个先进先出的队列(从桶的上面进，下面出)。

1）进行第一趟分配和收集，要按照最后一位（个位）分配。

分配过程如下(注意，关键字从桶的上面进入)：

80的最低位是0放入桶0、43最低位是3放入桶3、155最低位是5放入桶5…以此类推，第一趟分配结果如下图：

收集过程是这样的：按桶0到桶9的顺序收集，注意关键字从桶的下面出。
桶0：80，100，0
桶1：31
桶2：没有关键字不收集
.
.
.
桶9：299
将每桶收集的关键字依次排开，所以第一趟收集后的结果为：
80，100，0，31，43，155，155，6，987，299
注意观察，最低位有序了，这就是第一趟基数排序后的结果。

2）在第一趟排序结果的基础上，按照十位进行分配

80的十位是8放入桶8、100的十位是0放入桶0、0的十位是0放入桶0…以此类推，第二趟分配结果如下图：

依次收集各个桶内数据结果如下：
100，000，006，031，043，155，155，080，987，299
注意观察，十位也已经有序了，这就是第二趟基数排序后的结果（为了方便观察，数字补0到同一长度）。

3）在第二趟的基础上进行第三趟分配收集（到了最高位百位，也是最后一趟）

100的百位是1放入桶1、000的百位是0放入桶0、006的百位是0放入桶0…以此类推，第三趟分配结果如下图：

依次收集各个桶内数据结果如下：
0，6，31，43，80，100，155，155，299，987

现在最高位有序，最高位相同的关键字按中间位有序，中间位相同的关键字按最低位有序，于是整个序列有序，基数排序过程结束。

代码实现

/**
 * @ClassName RadixSortDemo
 * @author: shouanzh
 * @Description 基数排序
 * @date 2022/5/10 20:31
 */
public class RadixSortDemo {
    public static void main(String[] args) {

        int[] array = new int[]{80, 43, 155, 987, 100, 31, 6, 299, 155, 0};

        radixSort(array);

        System.out.println(Arrays.toString(array)); // [0, 6, 31, 43, 80, 100, 155, 155, 299, 987]

    }


    /**
     * 基数排序（LSD 从低位开始）
     * @param array 数组
     */
    public static void radixSort(int[] array) {

        // 取得数组中的最大数，并取得位数
        int max = array[0]; // 假设第一个数就是最大的
        for (int item : array) {
            if (item > max) {
                max = item;
            }
        }
        // 最大数是几位数
        int maxLength = (max + "").length();


        // 定义一个二维数组，表示10个桶，每个桶就是一个一维数组，每个桶的长度为array.length
        int[][] buckets = new int[10][array.length];

        // 为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
        // 比如：bucketElementCounts[0] 记录的就是 buckets[0] 桶存放数据的个数
        int[] bucketElementCounts = new int[10];


        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // 针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位...
            for (int element : array) {
                // 取出每个元素个位的值
                int digitOfElement = element / n % 10; // 如获取十位数， 978 / 10 = 97 % 10 = 7
                // 放入到对应的桶
                buckets[digitOfElement][bucketElementCounts[digitOfElement]] = element;
                // 桶计数++
                bucketElementCounts[digitOfElement]++;
            }

            // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            // 遍历每一个桶，并将桶内数据放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中有数据，才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    // 循环该桶（即第K个一维数组）
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        // 取出元素，放入到array
                        array[index] = buckets[k][l];
                        index++;
                    }
                }
                // 处理完毕后，将桶计数bucketElementCounts[k] 清0
                bucketElementCounts[k] = 0;
            }

            System.out.println("第" + (i + 1) + "轮排序：" + Arrays.toString(array));

        }
    }

}

运行结果

第1轮排序：[80, 100, 0, 31, 43, 155, 155, 6, 987, 299]
第2轮排序：[100, 0, 6, 31, 43, 155, 155, 80, 987, 299]
第3轮排序：[0, 6, 31, 43, 80, 100, 155, 155, 299, 987]
[0, 6, 31, 43, 80, 100, 155, 155, 299, 987]