Java语言实现基数排序代码分享

什么是基数排序

基数排序（Radix Sort）是一种线性的时间复杂度的排序算法，它的速度比冒泡排序、插入排序、选择排序等算法都快，但是没有快速排序和归并排序快。基数排序是根据排序元素的每一个数位来排序元素的算法，时间复杂度为O(dn)，其中d为元素位数。

基数排序的思路

基数排序依次对文本的排序关键字的每一位进行排序，从高位到低位，通过优先级的过滤选择、字符和存储区分、记录的堆垛化等处理技术，达到快速排序的效果。其基本思路如下：

1. 扫描一遍序列，找出序列中最大的位数，确定序列需要比较的次数，以确定排序的轮数。
2. 每一轮都从低位到高位进行排序。
3. 需要一个额外的数组作为存储空间，用于存放每一位子关键字排好序的元素。

基数排序的实现

Java语言的基数排序主要实现分为两步：

1. 扫描一遍序列，找出序列中最大的位数，确定序列需要比较的次数，以确定排序的轮数。
2. 由低位到高位，对序列每一位子关键字分别进行排序。

下面是Java语言实现基数排序的代码：

public class RadixSort {
    /**
     * 基数排序主体代码
     *
     * @param arr 待排序数组
     */
    public static void radixSort(int[] arr) {
        // 找出数组最大值
        int max = arr[0]; 
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        // 确定最大值的位数
        int digitNum = 1;
        while (max / 10 > 0) {
            digitNum++;
            max /= 10;
        }
        // 排序
        for (int i = 0, mod = 10, div = 1; i < digitNum; i++, mod *= 10, div *= 10) {
            // 初始化桶
            int[][] bucket = new int[mod * 2][0];
            // 将arr中的元素放入桶中
            for (int j = 0; j < arr.length; j++) {
                int digit = arr[j] % mod / div + mod;
                bucket[digit] = arrayAppend(bucket[digit], arr[j]);
            }
            // 将桶中元素复制回arr中
            int index = 0;
            for (int j = 0; j < bucket.length; j++) {
                for (int k = 0; k < bucket[j].length; k++) {
                    arr[index++] = bucket[j][k];
                }
            }
        }
    }

    /**
     * 数组扩容，用于放入桶中
     *
     * @param arr   数组
     * @param value 值
     * @return 扩容后的数组
     */
    public static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    /**
     * 示例一：基数排序排序int数组
     */
    public static void demoOne() {
        int[] arr = {53, 3, 542, 748, 14, 214, 154, 63, 616};
        System.out.println("待排序数组：" + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后数组：" + Arrays.toString(arr));
    }

    /**
     * 示例二：基数排序排序String数组
     */
    public static void demoTwo() {
        String[] arr = {"bcdef", "dbaqc", "abcde", "omadd", "bbbbb"};
        System.out.println("待排序数组：" + Arrays.toString(arr));
        String[] sortedArr = radixSort(arr);
        System.out.println("排序后数组：" + Arrays.toString(sortedArr));
    }

    public static void main(String[] args) {
        demoOne();
        demoTwo();
    }
}

运行结果

示例一

执行demoOne()方法后，输出结果如下：

待排序数组：[53, 3, 542, 748, 14, 214, 154, 63, 616]
排序后数组：[3, 14, 53, 63, 154, 214, 542, 616, 748]

示例二

执行demoTwo()方法后，输出结果如下：

待排序数组：[bcdef, dbaqc, abcde, omadd, bbbbb]
排序后数组：[abcde, bbbbb, bcdef, dbaqc, omadd]

总结

基数排序的核心思想是按照数字的位数依次排序。虽然它的时间复杂度为O(d*n)，但是实际上跑起来很快，因为不管原数组中数字的多少，数字的位数是有限的。因此，如果我们知道数据的范围并且数据位数是有限的，那么我们可以使用基数排序来使算法更快。