排序算法的第四章——归并排序。归并排序涉及到了「分治」，其中的合并操作，更是一种非常常见的处理方法。同时使用场景也不再单单是使用在排序中，还可以用于...

这是我们学习的第四个排序算法，归并排序算法。经过我们前面的学习我们已经学习了：

1. 冒泡排序
2. 选择排序
3. 插入排序

它们的时间复杂度都为O(N2)O(N^2)O(N2),空间复杂度为O(1)O(1)O(1)。算法性能上并没有孰强孰弱，不过在「稳定性」上存在差别。

• 冒泡、插入排序能保证「稳定性」
• 插入排序不能保证「稳定性」

相信有的同学有疑问：前面学习的这3个排序的时间复杂度都指数级别的，有没有更快的排序算法呢？？

答案是：肯定有的。

今天我们就来学习比前面排序更快的算法：归并排序。

算法描述

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。—— 百度百科

根据上述描述我们可以得到两个关键字：

1. 分治
2. 归并

分治

在算法中，分治是一种解决问题的通用策略，它的基本思想是将一个大问题分解成若干个相同或相似的子问题，然后分别解决这些子问题，最后将子问题的解合并起来，得到原问题的解。分而治之

分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

分治策略通常包含三个步骤：

1. 分解（Divide）： 将原问题分解成若干个规模较小的子问题。这一步骤通常通过递归来实现，将大问题不断分解为更小的子问题。
2. 解决（Conquer）： 分别解决每个子问题。这一步骤可以是递归调用算法本身来解决子问题，或者使用其他合适的方法来解决。
3. 合并（Combine）： 将子问题的解合并成原问题的解。这一步骤通常涉及将子问题的解组合起来，以得到原问题的解。

分治策略在解决许多问题时都非常有效，特别是那些可以被分解成相似子问题的问题。一些经典的算法和问题，如归并排序、快速排序、汉诺塔问题、最大子数组问题等都可以通过分治策略来解决。

归并

归并其实就是将子问题的解合并起来，分治里面包含了归并这一步骤。那么我为什么要单独把他拎出来呢？这是因为在很多题目里面并没有涉及到「分治」而是这又单纯的「归并」或者「合并」操作，所以我们还是要掌握和理解这个归并的操作的。

归并排序是「分治」的应用，将待排数组递归或者迭代地分为左右两半，直到数组长度为1，然后合并左右两个数组，在合并中进行排序操作。

稳定性

归并排序的稳定性在于合并时，两个相等的元素我们可以判断，当左右两个数组前的元素相等时，左边的元素总会被放在左侧来保证其是稳定的。类似If(left[i]<=right[j])

代码实现

实现归并排序可以有两种方式来实现：

1. 自顶向下：从输入数组出发，不断二分该数组，直到数组长度为1，在执行合并。适合用递归实现。
2. 自底向上：从输入数组的单个元素出发，一一合并，二二合并，四四合并直到数组有序。适合用迭代实现。

然后数组合并也有两种方式来实现：

1. 原地合并。
2. 非原地合并（借用一个数组）。

两两组合就有四种方式实现：

1. 自顶向下原地。
2. 自顶向下非原地。
3. 自底向上原地。
4. 自底向上非原地。

这里我们采用第二种「自顶向下非原地」，其它三种大家可以学有余力的了解一下，想看的也可以评论区评论哦。

class Solution {
    //临时数组
    int[] temp;
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        //初始化临时数组
        temp = new int[n];
        sort(nums,0,n-1);
        return nums;
    }

    //数组的边界[l,r]
    public void sort(int[] q,int l,int r){
        //当l左边界大于等于r是返回。
        //l>r时出现越界。
        //l=r时数组长度为1。直接返回
        if(l>=r) return;
        //求出当前数组的中间下标。l+(r-l)/2防止值溢出
        int mid = l+(r-l)/2;
        //定义指标，i、j。
        //i为左数组的第一个下标。j为右数组的第一个下标。
        int i = l,j = mid+1; 
        //临时数组第一个下标
        int k = 0;
        //递归
        sort(q,i,mid);
        sort(q,j,r);

        //合并操作，左数组下标的范围为[i,mid]、右数组下标的范围为[j,r]
        while(i<=mid&&j<=r){
            //将左右数组中小的值添加到temp中。
            if(q[i]<=q[j]) temp[k++] = q[i++];
            else temp[k++] = q[j++];
        }

        //防止出现另一个数组中的元素还没有添加到temp中
        //例如temp中一直添加的是右数组中的元素，j>r结束循环了。导致左数组的元素还没有添加到temp中。
        //反之亦然。
        while(i<=mid)  temp[k++] = q[i++];
        while(j<=r) temp[k++] = q[j++];

        //将temp中的值合并到原数组中
        for(i=l,j=0;i<=r;++i,++j) q[i] = temp[j];
    }
}

上述代码中求中间坐标mid使用的是int mid = l+(r-l)/2是为什么呢？为什么不是int mid = (l+r)/2呢？

其实两种是相等的，如果将第一种进行合并得到的结果就是(l+r)/2那么为什么这样做呢？

其实这个技巧非常常用，特别是在「二分查找」中，这样的目的其实是为了防止出现「数值溢出」。

我们要知道在java中int的最大值是2147483647，虽然一般的算法题目会给出数据范围，如果超出了int范围的结果都会返回long或者是对结果进行取模操作。但是它就是会出现这种情况（算法题目经常出现这种用例）：

1. l=2147483646
2. r=2

两者相加l+r就超出了int的最大范围，导致出现数值溢出。所以我们可以使用int mid = l+(r-l)/2来进行避免。

时间空间复杂度

每次减半后的左右两半对应元素的对比和赋值总是必须的，也即在每一层递归中 (这里的一层指的是 递归树 中的层) ，比较和赋值的时间复杂度都是 O(n)O(n)O(n)，数组规模减半次数为 lognlognlogn，即递归深度为 lognlognlogn，也即总共需要 lognlognlogn 次 O(n)O(n)O(n) 的比较和赋值，时间复杂度为 O(nlogn)O(nlogn)O(nlogn)。

递归深度为 lognlognlogn，递归过程中需要一个长度为 nnn 的临时数组保存中间结果，空间复杂度为 O(n)O(n)O(n)。

归并操作应用

前面说到「归并」这种合并操作是经常用到的。剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）

这一题其实就是将我们排序中的数组换成了链表。合并的方式都是一样的，定义两个指针分别遍历两个链表，然后将小的链表节点作为我们的新链表的尾节点。不过需要注意的是，同合并数组一样，同样会出现另一个遍历完了，导致这个没有全部添加到新链表中的处理。不过不同于数组的是，链表只需要将没有遍历完的节点当做新链表的尾节点就行了。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p1 = l1,p2 = l2;
        ListNode s = new ListNode();
        ListNode cur = s;
        while(p1!=null&&p2!=null){
            //p1的val小于p2的val
            if(p1.val<p2.val){
                //添加p1节点
                cur.next = p1;
                //移动p1指针
                p1 = p1.next;
            }else{
                //添加p2节点
                cur.next = p2;
                //移动p2指针
                p2 = p2.next;
            }
            //移动cur指针
            cur = cur.next;
        }
        //p1没有遍历完
        if(p1!=null) cur.next = p1;
        //p2没有遍历完
        if(p2!=null) cur.next = p2;
        return s.next;
    }
}

剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode） 大家也可以看下这个写的非常好的题解，用来理解这个「合并」 的过程。

归并排序应用

大家可能会疑问？这排序算法的应用场景不就是用在于「排序」上吗？为啥还有别的应用。

没错排序算法的应用场景就是用于「排序」上的，不过归并排序这个过程中，是可以专门处理一类场景问题的。即「逆序对」问题。

什么是「逆序对」问题呢？？ 我们通过这道题就知道了剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

那么这道题我们应该怎么处理呢？？天哪！还是困难题~

题目中的五组「逆序对」为：

1. 7-5
2. 7-6
3. 7-4
4. 5-4
5. 6-4

我们可以在「合并」阶段。本质上是 合并两个排序数组  的过程，而每当遇到 左子数组当前元素 > 右子数组当前元素 时，意味着 「左子数组当前元素 至 末尾元素」 与 「右子数组当前元素」 构成了若干 「逆序对」 。

class Solution {

    public int reversePairs(int[] nums) {
        temp = new int[nums.length];
        return sort(nums,0,nums.length-1);
    }
    int[] temp;
    int sort(int[] q,int l,int r){
        if(l>=r) return 0;
        int mid = l+r>>1;
        int res = sort(q,l,mid) + sort(q,mid+1,r);
        int k =0,i=l,j = mid+1;
        //合并
        while(i<=mid&&j<=r){
            if(q[i]<=q[j]) temp[k++] = q[i++];
            else {
                temp[k++] = q[j++];
                //计算逆序对
                res += (mid-i+1);
            }
        }
        while(i<=mid) temp[k++] = q[i++];
        while(j<=r) temp[k++] = q[j++];
        for(i=l,j=0;i<=r;i++,j++) q[i] = temp[j];
        return res;
    }
}

所以看到求「逆序对」就要想起「归并排序」~

总结

1. 归并排序的核心思想就是在于「分治」。
2. 「分治」是分为若干个规模较小的子问题。这一步骤通常通过「递归」来实现。（递归是初学者比较难以理解的一个概念，大家学习递归的时候可以试着用图来画出步骤比较小的递归过程，加深理解。）
3. 归并排序的时间复杂度相比前面几种是有所提高的O(nlogn)O(nlogn)O(nlogn)。
4. 归并排序是可以保证其排序的「稳定性」的。
5. 归并排序的场景不仅是运用在「排序」，还可以使用在计算「逆序对」。