JAVA十大排序算法之基数排序详解

基本概念

基数排序是按照低位先排序，也就是先排个位，再排十位，以此类推。这样从最低位开始排序，直到最高位排序完成之后，数列就变成了一个有序序列。

算法步骤

基数排序的过程可以描述如下：

1. 取得数组中的最大数，并取得位数；
2. arr为原始数组，从最低位开始取每个位组成radix数组；
3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
4. 将排序好的radix数组重新构建为原数组arr；

代码实现

public static void radixSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    //取得数组中的最大数
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    //取得最大数的位数
    int digit = 1;
    while(max / 10 > 0) {
        digit++;
        max /= 10;
    }
    //初始化桶
    int[][] bucket = new int[10][arr.length];
    //存储每个桶中存放了几个数据
    int[] count = new int[10];
    //从低位到高位依次处理
    for(int i = 0; i < digit; i++) {
        //放入桶中
        for(int j = 0; j < arr.length; j++) {
            int num = arr[j] / (int)Math.pow(10, i) % 10;
            bucket[num][count[num]] = arr[j];
            count[num]++;
        }
        //取出桶中的数据
        int index = 0;
        for(int j = 0; j < 10; j++) {
            if(count[j] != 0) {
                for(int k = 0; k < count[j]; k++) {
                    arr[index++] = bucket[j][k];
                }
            }
            //桶清零
            count[j] = 0;
        }
    }
}

算法分析

时间复杂度：O(d * n)，其中 d 为位数，n 为数字个数。由于基数排序需要借助一些存储空间来进行排序，因此空间复杂度较高，为 O(n + d)。

示例说明

示例1

输入：[3, 5, 1, 4, 2, 6, 7, 9, 8]

输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

说明：计算出最大数为9，然后进行两轮排序，第一轮按照个位进行排序，第二轮按照十位进行排序，最终得到有序数组。

示例2

输入：[1234, 56, 89, 123, 123456]

输出：[56, 89, 123, 1234, 123456]

说明：对于位数不同的数，需要进行补全操作，如56补全为00056，然后再正式进行排序。