Java基数排序

基数排序图示

  基数排序（radix sort）是一种 非比较型 排序算法，属于“分配式排序”（distribution sort），一般用于排序正整数序列，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
  基数排序（radix sort）是桶排序的升级版。

实现思路：

• 首先需要定义一个二维数组长度为 10 代表 0~9，宽度为待排序数组的长度。
• 找到待排序数组中的最大值，获取最大数的位数，这决定了需要进行多少轮排序。
• 排序从个位开始，依次向前递增，根据对应位数的值决定该数放入哪个桶中。
• 一轮排序结束后，需要将桶中的数据依次取出，放入原数组。

参考代码

public static void radixSort(int[] arr) {
    // 二维数组，存放 10 个桶和各桶中的元素
    int[][] bucket = new int[10][arr.length];
    // 一维数组，记录每个桶中元素的个数
    int[] elementCounts = new int[10];
    // 获取待排序数组中最大数
    int max = 0;
    for (int num : arr) {
        if (max < num) max = num;
    }
    // 获取最大数的位数 ==> 转成字符串求长度
    int digits = ("" + max).length();
    // 排序，K 为当前比较位数，个、十、百、千...
    for (int i = 0, k = 1; i < digits; i++, k *= 10) {
        // 将 arr 中的数据按规则放入桶中
        for (int num : arr) {
            int m = num / k % 10;  // 第 m 个桶
            int n = elementCounts[m];  // 第 m 个桶中的第 n 个位置
            bucket[m][n] = num;
            elementCounts[m]++;
        }
        // 将桶中的数据依次放回 arr 中，进行下一轮排序
        int index = 0;
        for (int j = 0; j < 10; j++) {  // 一共 10 个桶
            if (elementCounts[j] == 0) continue;  // 如果第 j 个桶中的元素个数为 0，换下一个桶
            for (int l = 0; l < elementCounts[j]; l++) {
                arr[index] = bucket[j][l];
                index++;
            }
            elementCounts[j] = 0;  // 元素个数清零
        }
    }
}

排序效果测试

public static void main(String[] args) {
    int[] arr = {1, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    System.out.println("排序前：" + Arrays.toString(arr));
    radixSort(arr);
    System.out.println("基数排序：" + Arrays.toString(arr));
}

1000 万随机数据测试排序时间

public static void main(String[] args) {
    int[] arrTime = new int[10000000];
    for (int i = 0; i < 10000000; i++) {
        arrTime[i] = (int) (Math.random() * 10000000);
    }
    long former = System.currentTimeMillis();
    radixSort(arrTime);
    long later = System.currentTimeMillis();
    System.out.println("时间：" + (later - former) + " 毫秒");
}

• 基数排序十分消耗内存，1亿数据会直接报错 java.lang.OutOfMemoryError: Java heap space
• 一般用于排序正整数序列，如果要处理含负数和小数的情况，需要再增加桶。