关于算法:看动画学算法之排序基数排序

之前的文章咱们讲了 count 排序，然而 count 排序有个限度，因为 count 数组是无限的，如果数组中的元素范畴过大，应用 count 排序是不事实的，其工夫复杂度会收缩。

而解决大范畴的元素排序的方法就是基数排序。

什么是基数排序呢？

考虑一下，尽管咱们不能间接将所有范畴内的数字都应用 count 数组进行排序，然而咱们能够思考按数字的位数来进行 n 轮 count 排序，每一轮都只对数字的某一位进行排序。

最终依然能够失去后果，并且还能够解脱 count 数组大小的限度，这就是基数排序。

如果咱们当初数组的元素是：1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。

先看动画，看下最直观的基数排序的过程：

在下面的例子中，咱们先对个位进行 count 排序，而后对十位进行 count 排序，而后是百位和千位。

最初生成最终的排序后果。

因为基数排序实际上是别离按位数的 count 排序。所以咱们能够重用之前写的 count 排序的代码，只是须要进行一些革新。

doCountingSort 办法除了传入数组外，还须要传入排序的位数 digit，咱们用 1，10，100，1000 来示意。

看一下革新过后的 doCountingSort 办法：

   public void doRadixSort(int[] array, int digit){
        int n = array.length;

        // 存储排序过后的数组
        int output[] = new int[n];

        // count 数组，用来存储统计各个元素呈现的次数
        int count[] = new int[10];
        Arrays.fill(count,0);
        log.info("初始化 count 值:{}",count);

        // 将原始数组中数据呈现次数存入 count 数组
        for (int i=0; i<n; ++i) {count[(array[i]/digit)%10]++;
        }
        log.info("count 之后 count 值:{}",count);

        // 这里是一个小技巧，咱们依据 count 中元素呈现的次数计算对应元素第一次应该呈现在 output 中的下标。// 这里的下标是从右往左数的
        for (int i=1; i<10; i++) {count[i] += count[i - 1];
        }
        log.info("整顿 count 对应的 output 下标:{}",count);
        // 依据 count 中的下标，构建排序后的数组
        // 插入一个之后，相应的 count 下标要减一
        for (int i = n-1; i>=0; i--)
        {output[count[(array[i]/digit)%10]-1] = array[i];
            count[(array[i]/digit)%10]--;
        }
        log.info("构建 output 之后的 output 值:{}",output);

        // 将排序后的数组写回原数组
        for (int i = 0; i<n; ++i)
            array[i] = output[i];
    }

跟 count 排序变动不大，区别就是这里咱们须要应用 count[(array[i]/digit)%10]，来对每一位进行排序。

另外，为了计算出位数 digit 的值，咱们还须要拿到数组中最大元素的值：

public int getMax(int[] array)
    {int mx = array[0];
        for (int i = 1; i < array.length; i++)
            if (array[i] > mx){mx = array[i];
            }
        return mx;
    }

看下怎么调用：

    public static void main(String[] args) {int[] array= {1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793};
        RadixSort radixSort=new RadixSort();
        log.info("radixSort 之前的数组为:{}",array);
        // 拿到数组的最大值，用于计算 digit
        int max = radixSort.getMax(array);
        // 依据位数，遍历进行 count 排序
        for (int digit = 1; max/digit > 0; digit *= 10){radixSort.doRadixSort(array,digit);
        }
    }

看下输入后果：

很好，后果都排序了。

从计算过程咱们能够看出，基数排序的工夫复杂度是 O(d*(n+b))，其中 b 是数字的进制数，比方下面咱们应用的是 10 进制，那么 b =10。

d 是须要循环的轮数，也就是数组中最大数的位数。如果数组中最大的数字用 K 示意，那么 d =logb(k)。

综上，基数排序的工夫复杂度是 O((n+b) * logb(k))。

当 k <= n^c，其中 c 是常量时，下面的工夫复杂度能够近似等于 O(nLogb(n))。

思考下当 b = n 的状况下，基数排序的工夫复杂度能够近似等于线性工夫复杂度 O(n)。

本文的代码地址：

learn-algorithm

本文已收录于 http://www.flydean.com/algorithm-radix-sort/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！

关于算法:看动画学算法之排序基数排序

简介

基数排序的例子

基数排序的 java 代码实现

基数排序的工夫复杂度