排序算法（六）归并排序

排序算法（六）归并排序

归并排序算法是分治算法的一个典型。所谓分治算法就是把一个复杂的问题分成多个子问题。这些子问题如果都解决了，这个复杂的问题也就解决了，这是典型的先分后治的思路。归并排序也算得上是一个比较复杂的算法了，说实话原理容易看懂，但到底是如何解决的可要大费脑筋了。

归并排序的基本介绍

你或许看到了，是否牛逼那一块我写的是是，那这个算法也就是我们第一个接触到的，流弊的排序算法，因为速度是很快的。同时你也可以看到空间复杂度是O(n)，要知道很多复杂的算法以及各种各样的缓存机制，数据库等等都是使用空间来换取时间的，不过这样也并不意味着排序算法的时间复杂度可以变成O(1)，算法导论中有证明，排序算法的最低时间复杂度是O(nlogn)。

归并排序的基本思路

归并排序的思路很难将明白，但是举个列子就很好说了。假如有待排序的数组4 1 2 5 8 7 6 0.我们找到mid((left+right)/2)先将其分为两个数组4 1 2 5和8 7 6 0（实际上我们并没有真的的分为两个数组，操作的始终是原来的那个数组）,然后再分为 4 1，2 5,8 7,6 0，然后继续分成 4,1,2,5,8,6,7,0.到这儿你或许会说，卧槽你这不是玩我的嘛，分了半天就是把数组之间加上逗号？玩蛇皮？其实我们的目的不在于分，而在于治。将 4 和 1 排成一个有序的数组简单不？就是 1 4 同理第一轮治理数组就变成了1 4 2 5 7 8 0 6然后再将1 4 和 2 5排序 7 8 和0 6排序。数组变成了1 2 4 5 0 6 7 8最后对1 2 4 5 和0 6 7 8 排序。数组变成了0 1 2 4 5 6 7 8，这样就变得有序了。

你或许在想，卧槽！这什么垃圾算法？这个速度也能快？这能叫流弊算法？

但是人家是真的快啊，而且你没有注意到的是，我们始终在做一件事情，把两个有序的数组合并为一个有序的数组。这就是这个问题的子问题，我们只有解决了这个问题也就解决了排序这个复杂的问题了。把两个有序的数组合并为一个有序的数组真的是一件简单的事情，只需要一个额外的临时的数组的帮助就可以轻松的解决。

看了下面的这个图，应该就很容易理解了。把数组中的元素往下放就是下面有一个临时数组。

归并排序的代码实现

首先我们先来完成治的过程，两个有序数组的合并

“治”的代码实现

public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;// 左边有序序列的初识索引
        int j = mid+1;// 右边有序序列的初识索引
        int t = 0;// 指向temp临时数组当前的序列
        // 将左面和右面的值按照大小放入到临时的数组当中去
        while (i <= mid && j<=right) {
            if (arr[i] <= arr[j]) {
                temp[t] = arr[i];
                ++t;
                ++i;
            }else {
                temp[t] = arr[j];
                ++t;
                ++j;
            }
        }

        // 如果左面还剩下数据的话，直接放入临时数组中，此时右面的已经都放入了临时数组中。（上面while退出就是一个已经放完了）
        while(i <= mid) {
            temp[t] = arr[i];
            ++t;
            ++i;
        }

        // 同理，左面为空，右面还有数据，直接放入临时数组当中
        while (j <= right) {
            temp[t] = arr[j];
            ++t;
            ++j;
        }

        // 将temp拷贝到原始的数组当中去。注意放入临时数组的范围是从left到right
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft] = temp[t];
            ++t;
            ++tempLeft;
        }

    }

代码说明：

1. 函数的参数是？？

   • 首先需要说明的是，数组其实是没有分的，只是逻辑上分为了几个数组，待合并的数组也还都是相邻的。
   • left是左边有序数组的开始 mid是中间的那个数，也就是(left+right)/2，需要注意的是，mid这个位置的值是属于前面的那个数组的，所以说右边有序数组的开始是mid+1。right是待合并的数组的结束。也就是说这个函数操作的只是数组的arr[left]到arr[right]而已。
   • temp 是用来辅助排序的临时数组

2. 第一个while循环在干啥？

   很好理解第一个while循环是不停的把两个有序数组中的元素放入临时数组中去，直到有一个数组为空了，就退出while循环。这时，我们就可以直接把不为空的那个数组放入到临时数组的后面。于是便有了后面的两个while循环。

3. 最后一个while循环是?

   把临时数组中的元素拷贝到待排序数组的left到right上。我前面说过，数组其实并没有真正分为两个，只是逻辑上分为两块而这一个函数操作的就只是数组的left到right。也就是说一个函数只是解决了一个子问题。

“分”的代码实现

public static void mergeSortHelper(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right)/2; // 找到中间值，开始分治
            mergeSortHelper(arr, left, mid, temp);
            mergeSortHelper(arr, mid+1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

public static void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];
        mergeSortHelper(arr, 0, arr.length-1, temp);
    }

代码说明：

1. 这我咋有点看不懂？

   虽然治才是分治法的核心但是这里的分确实是有点不好理解。不好理解的主要原因是你对递归的了解还不够透彻。上面将数组分为了两个部分，然后合并。

2. 一开始左右不是无序的吗？怎么能合并呢？

   这就是我所说的递归的理解了。执行到第一个mergeSortHelper时会一直递归，递归到left == right退出递归。执行下面的第二个mergeSortHelper，需要注意的是此时位于的是退出的那个栈的前一个栈，也就是right - left == 1的那个栈。回到那个栈之后又是一直递归。又到了left == right又退出了递归。那么执行到第三个合并的时候位于那个栈呢？此时第一个mergeSortHelper的栈都位于底部。最上面的那个栈是left = 0，mid =0， right=1。为什么呢？因为退出的那个栈是left == right而这个right就是上一层的mid 也就是说mid = (left + right)/2是为0的。而这个栈是没有退出的也就是说left < right。所以right =1；。。。。我特喵的再将什么。算了不说这个递归过程是如何的了。直接通俗的将一下吧。

3. 我听不懂你乱七八糟的说辞，可以讲的简单一点吗？

   双递归函数本来就有点乱，况且后面还带了一个函数，我理解的也不是很透彻。简单的将就是mergeSortHelper的作用是left到right变得有序，第一个mergeSortHelper因此就是使左面有序，第二个是使右面有序，第三个是使左右两个有序的合并。

4. 这也行？讲的也太敷衍了吧。。。

   其实一点都不敷衍，你看看其他的两次递归算法。比如斐波那契数列，汉罗塔问题。不都是这样解决的吗？

斐波那契数列代码

public static int fibonacci(int n){
    return (n==1 || n==2)?1:fibonacci(n-1)+fibonacci(n-2);
}

汉罗塔问题代码

public static void hanoi(int n,char a, char b, char c){
    if (n == 1){
        System.out.println(a+"->"+c);
    }
    hanoi(n-1, a, c, b);
       System.out.println(a+"->"+c);
    hanoi(n-1, b, a, c);
}

上面的两串代码都是即兴瞎写的不保证对，但是思路是一样的。你说这些递归问题都是如何解决的呢？如果说斐波那契数列比较容易理解，这个肯定是可以算出的啊。那么汉罗塔问题呢？？这个问题够复杂了吧。将n个盘借助b从a移动到c，我们只需要分析子问题是什么——子问题是将n-1个盘借助c移动到b，然后将最大的那个盘从a移动到c，然后再借助a把n-1盘从b移动到c。这里我们只需要知道1个盘怎么移动，那么2个盘，3个盘就是999999个盘我们都可以知道。（如果有64个盘，有一个人知道如何移盘，假设他一秒移动一个盘子，那么移动到太阳系没了也不会移完的。）归并排序也是如此。当right只比left大一的话(此时不用多次递归)就可以合并这个数组，那么当right比left大得多的时候呢？不就是根据先把左右有序然后合并一样的道理吗？这就是递归解决问题的神奇之处。

归并排序的测试

测试环境及工具：我的电脑 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 Randon.nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        mergeSort(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");
}

80,000数据时：

• Time : 11ms
• Time : 12ms
• Time : 16ms

8,000,000数据时：

• Time : 1029ms
• Time : 1024ms
• Time : 1007ms

总结

可能是测试的时候电脑的问题，为啥归并排序排8,000,000还比快速排序慢啊，这个其实很意外，按照时间复杂度来说应该是归并排序快一点啊。不过再我多次测量了之后，速度稳定在1000ms，放弃了。唉~，只能说一句，快速排序牛逼！！