3.归并排序(Merge sort)

题目

设计一个算法可将{4, 2, -3, 6, 1} （或其他乱序的数组）按升序排序得到 {-3, 1, 2, 4, 6}。

解题思路

1.将数组分成两组
2.每一组各自排序，怎么排?用同样的方法排，重复动作(1)分成两组...（递归）
3.合并：经过1，2动作的递归后，最后会变成一颗树，再从树的最底层开始每两个节点开始合并, 合并的同时做好排序，当合并到最顶层时整个数组就排序好了。
如何排序：每个节点的数据都是由上一次合并后得到的是排序好的！我们可以把两个节点想象为有两个数组，每次对比两个数组的第一个元素取出较小的元素放到另一个数组里，当两个数组的元素都被取完了就完成排序和合并了。

(1),(2)

1.png

(3)

2.png
(排序合并)
排序.png

Code

    public void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int[] helper = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, helper);
    }


    //    1.将数组分成两组
//    2.每一组各自排序，怎么排?用同样的方法排，重复动作(1)分成两组...（递归）
    private void mergeSort(int[] arr, int left, int right, int[] helper) {
        //base case:如果节点只剩下一个元素了则停止分裂
        if (left >= right) {
            return;
        }

        //防止大数溢出,如果left和right都等于Integer.MAX_VALUE那么它们相加就会超出int的取值范围导致溢出
        int mid = left + (right - left) / 2;
        //分组
        mergeSort(arr, left, mid, helper);
        mergeSort(arr, mid + 1, right, helper);

        //合并
        megre(arr, left, mid, right, helper);
    }

    //3.合并：经过1，2动作的递归后，最后会变成一颗树，再从树的最底层开始每两个节点开始合并,
// 合并的同时做好排序，当合并到最顶层时整个数组就排序好了。
// 如何排序：每个节点的数据都是由上一次合并后得到的是排序好的！
// 我们可以把两个节点想象为有两个数组，每次对比两个数组的第一个元素取出较小的元素放到另一个数组里，
// 当两个数组的元素都被取完了就完成和排序和合并了。
    private void megre(int[] arr, int left, int mid, int right, int[] helper) {
        for (int i = 0; i < arr.length; i++) {
            helper[i] = arr[i];
        }
        int l = left;//表示左边数组的指针
        int r = mid + 1;//表示右边数组的指针
        int k = left;//存放排好序的元素的数组的指针
        while (l <= mid && r <= right) {//当有其中一个指针先走完则停止while循环
            if (helper[l] < helper[r]) {
                arr[k] = helper[l];//取出较小的元素放到另一个数组里
                k++;//指针右移
                l++;//指针右移
            } else {
                arr[k] = helper[r];//取出较小的元素放到另一个数组里
                k++;//指针右移
                r++;//指针右移
            }
        }

        //如果r指针先走完l指针还未走完则直接将元素放到另一个数组的尾部
        while (l <= mid) {
            arr[k++] = helper[l++];
        }

    }

时空复杂度分析

时间复杂度：

Merge sort的时空复杂度分析比较复杂，我们可以把这个算法的执行过程分为两个阶段来看:
第一个阶段：分组

1.png

从这张图中我们可以看出分组时的每一层的节点数都是上一层的double,所以总共的节点数是:1+2+4+8+...+n/2 = 1+1+2+4+8+...+n/2-1 = n/2 + n/2 -1 = n-1,忽略对复杂度影响较小的系数所以总节点是n，而且每次分组只执行了一行求mid的代码:
int mid = left + (right - left) / 2;也就是O(1), 所以第一阶段的时间复杂度是O(n*1) = O(n);

第二阶段：合并
我们来看看合并的核心代码

        while (l <= mid && r <= right) {
            if (helper[l] < helper[r]) {
                arr[k] = helper[l];
                k++;
                l++;
            } else {
                arr[k] = helper[r];
                k++;
                r++;
            }
        }

是一个while循环，随着arr数组的长度的增加while循环的次数是线性增长的所以我们得出这段代码的复杂度是O(n), 其实只要是while循环或者单层for循环我们都可以认为复杂度就是O(n)，既然每一层的复杂度是O(n)那么我们只要算出总共有多少层就可以算出第二阶段的时间复杂度，如上图我们假设这是一棵满的二叉树那么就总共有log2n层，或者假设数组的长度n=8每次二分总共可以分裂log2n次，所以第二阶段的时间复杂度是O(nlgn). （lgn = log2n）

结论：所以merge sort的时间复杂度是O(n)+O(nlgn),因为我们关心的是渐进性复杂度有高次项在的时候可以忽略低次项，所以O(n)<O(nlgn)取O(nlgn)。

空间复杂度：

因为是megre sort是递归实现的，所以空间复杂度与其递归的层数相关，先普及一个概念: 在java中每一个函数的开始和结束都代表着在JVM Stack中一个栈帧(stack frame)的入栈和出栈，递归是函数自己调用自己，每次调用自己都会往JVM Stack中压入一个stack frame

stack_frame.png

因为megre sort的递归树总共有lgn层，所以我们最多时使用了lgn个stack frame，so空间复杂度是O(lgn)。
但是我们这段merge sort代码的空间复杂度并不是O(lgn)而是O(n),
为什么呢？因为我们除了必须要使用到的局部变量外还创建了一个辅助我们计算的数组int[] helper = new int[arr.length]; ，所以空间复杂度应该是：O(lgn)+O(n)而O(lgn)<O(n), 所以我们megre sort的空间复杂度是O(n)。(我们关心的是渐进性复杂度有高次项在的时候可以忽略低次项)