排序算法（七）基数排序

排序算法（七）基数排序

这里说的是基数排序(Radix Sort)而不是计数排序(Counting Sort)，计数排序也是另外的一种比较高效的排序算法，但是这个算法不在我近阶段要讲的算法之列。说起和基数排序类似的算法，桶排序(Bucket Sort)其实就是和基数排序是有点儿相似的，不过桶排序也不在近阶段介绍之列，蛤蛤蛤~~(⊙o⊙)…

基数排序的的基本介绍

我们发现这个基数排序的时间复杂度似乎是比O(nlogn)要低的，但是这个O(nlogn)是比较类的排序算法的下限，基数排序是一种典型的使用空间来换取时间的算法，不属于比较类排序算法。另外要说的是，基数排序是一个稳定的算法。

基数排序的基本思路

基数排序的基本思路是准备十个桶。从0号桶到9号桶。第一次我们使用个位数进行排序，然后把数据从桶中依次取出来。第二次使用百位数进行排序。。。以此类推就这样这个数组就是有序的了。这个思路还是比较容易理解的。

下面直接上图吧。

再来一个图片看一下子

这个算法算是一般流弊算法吧。因为特别容易理解，没啥需要理解的，搞得我都不知道要说什么啦。。。

直接来上代码看代码的实现吧。

基数排序的代码实现

    public static void radixSort(int[] arr) {
        int[][] backet = new int[10][arr.length];
        int[] backetElementsCounts = new int[10];

        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // 下面两种方法都可以选择 转为字符串求数字的长度
        int maxLength = (max+"").length();
//        int maxLength = Integer.toString(max).length();

        for (int i = 0, t=1; i < maxLength; i++, t*=10) {
            // 数据放入桶中
            for (int j = 0; j < arr.length; j++) {
                int which_backet = arr[j]/t%10;
                backet[which_backet][backetElementsCounts[which_backet]++] = arr[j];
            }

            // 把数据从桶中取出
            for (int j = 0, k=0, m=0; j < 10; j++) {
                while (backetElementsCounts[j] != 0) {
                    arr[k] = backet[j][m];
                    backetElementsCounts[j]--;
                    k++;
                    m++;
                }
                m=0;
            }

        }
    }

代码说明：

1. 第三行代表的含义是什么？

   第二行代码其实就是在造桶子，十个桶子，每个桶子的大小的都是arr.length，因为万一所有的数的某一位都是相同的，那个桶子不就爆了喵？？而第三行的数组是存放每个桶子中的元素的个数。因为下面还是要取出元素的，不知道放了几个元素，怎么取，玩蛇皮的嘛。

2. 为什么要求最大的数字的长度？

   这个把数字转为字符串来求长度还是非常的妙的。不过你问为啥要求最大的数字的长度？？因为后面我们要从个位数开始根据每个位置开始排序啊。

3. t的作用是什么？

   第一次取到个位数就是 num/1%10。取百位数就是 num/10%10。我们通过每次t /= t就可以依次取到各个位数了。每次放入一个元素之后，对应的用来计数的数组中的值也要增加1.

4. 如何取出数据的？

   这恐怕是更容易理解的。找到桶里有数据的桶，看看桶中有几个数据取出来放到原来的数组中不就完事了。

   唉~，这个算法是实在简单，搞得我是真的没话说了。我也是醉了吖。。。

基数排序的测试

测试环境及工具：我的电脑 Huawei MateBook 13+JDK1.8+Eclipse

测试手段：随机生成80000个和8,000,000个[0,800000）的整数的数组进行排序，观察所花费的时间

测试代码：

public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random()*800000);
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        radixSort(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");
}

80,000数据时：

• Time : 12ms
• Time : 16ms
• Time : 17ms

8,000,000数据时：

• Time : 423ms
• Time : 397ms
• Time : 404ms

总结

可以清楚的看到排八万个这种小数据的时候，几种高效的算法几乎没有区别。不过排八百万个数据的时候，基数排序就发挥出了他的优势。快啊！不过要说明的是，基数排序极其占用内存，如果是排序八千万个数耗费的就是4个G左右的内存，所以说在内存不足的情况下，这个算法是不适合考虑的。