前言&复习
今天是我们0基础算法课的第二节课，今天我想给大家分享的知识是归并排序。
首先我们先来回顾一下上次课我们所学习的内容，我们在第一节课为大家讲了快速排序，在上节课中，我们了解到快速排序是排序效率在同为O(N*logN)的几种排序方法中效率较高，然后我们才用分治的方法去实现快速排序。其中的三个步骤相信大家都还记得：确认边界点-重新调整区间-递归。之后为大家举了实例并重新顺了一遍思路，就开始进行模板的实现，模板在这里是要求大家记住的，学会了模板之后，我们在遇到排序的时候，只需在主函数中输入输出相关内容，排序的时候直接调用我们的模板就可以了。
上节课大概就讲了那么多内容，如果有什么你没有掌握或者说你还不会的知识，可以直接从这里跳转到我的上一节课中去学习：https://developer.aliyun.com/article/1003294?spm=a2c6h.13262185.profile.6.64c56283kG8a5D
接下来我们就开始归并排序的讲解。
知识讲解
什么是归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
好，这句话已经向我们传达很多信息了，第一采用了分治法，这个名字很熟悉吧，我们在实现快速排序的时候也是使用的分治法，所以在这里就不作讲解了；其次提到了一个归并操作，在这里我为大家解释一下归并操作。
归并操作
归并操作：指的是将两个顺序序列合并成一个顺序序列的方法。举例：假设有以下数列{7，19，35，92，63，2} ，初始状态就是这样：[7] [19] [35] [92] [38] [63] [2] ；第一次归并后：{7，19} {35， 92} {38， 63} {2} ；第二次归并后：{7， 19， 35， 92} {2， 38， 63} ；第三次归并后：{2， 7，19，35，38，63， 92} 。这个时候你也能理解到那个将两个顺序序列合并成一个顺序序列的方法了吧。
归并排序的特点
归并排序是一个稳定的排序算法，在进行子数组合并的时候，我们可以设置当元素大小相等时，先将前半部分的数据放入临时数组，这样就可以保证相等元素在排序后依然保持原来的顺序，并且归并排序的执行效率与原始数据的有序程度无关，其时间复杂度是非常稳定的，都是O(nlogn) 。
基本思路
前面也提到，我们在实现归并排序的时候使用的是分治法，其主要过程为：
- 将数组元素从中间划分开，分为两个部分。（中间点划分）
- 将分成的两部分，分别进行递归分解。直到所有部分的元素个数都为1。（递归排序）
- 自下而上的开始逐步合并两个排好序的数列。（合二为一）
我也将上面的过程简化为：中间点划分-递归排序-合二为一。三个步骤去进行实现。在这三个步骤中，我们将递归过程，以及排序的过程去填入到模板之中，也就形成了我们在下文中提到的模板代码部分了。
核心步骤演示
在我们三个阶段的主要过程中，其中第三步合二为一也是核心步骤，下面我就为大家演示以下核心步骤的实现。
合而为一就是将两个已经排序的数组合并为一个顺序的数组，其中我们可以利用双指针的方法去实现。
如图所示，首先我们这里有两个已经顺序的数组，下面我们创建出a,b两个指针分别只向两个数组的初始数，并创建一个新的数组C用于存放最终数组 。
之后我们对a指针指向数字与b指针指向数字进行比较，如果a指针指向的数字小，就将a指针指向的数字放入C，反之放入B；放入C之后，对应的指针就向后移一位，继续进行新的比较；直到一个数组全部被填入为止， 这是就将另一个数组剩余元素全部放入即可。
下面就逐步演示上一段话的内容：
首先进行比较(15>6）所以将6放入，并且b指针后移。
之后继续比较a和b（20>15）所以将15放入数组，并且a指针后移 。
继续进行比较（28>20),所以将20放入数组，并且b指针后移 。
继续进行比较（35>28),所以将28放入数组，并且a指针后移 。
之后就是一直这样进行比较，中间过程我直接跳过 。
......
这时经过多次操作后到了这个步骤 。
我们在经过比较（127>120)后将120填入，这时A数组的所有元素已经被全部填入。这时，我们就只需将B数组的剩余元素（126， 152）按顺序填入即可
所以，排序的结果就是这样的：
这时，我们就得到了一个完整的数组C是包含A，B数组所有元素的顺序数组。
归并排序实现
我们将归并排序的实现分为以下简单的三步：
1.输入相关数据 。
2.调用归并排序模板 。
3.输出要求输出的内容 。
想必大家13步都没有什么问题，就是cin cout 那些基础的语句，所有下面就重点讲一下我们归并排序的模板（merge_sort）
模板流程
在merge_sort模板中：
首先我们要找出我们的中点，也就是mid ；
之后我们就判断数组中的元素：当数组中的元素是一个或者没有时，返回即可。如果数组中的元素大于一个的话，我们就继续递归排左右边（也就是我们的最后一步） 。
最后我们设置两个指针i,j分别指向起点，之后进行比较，如果a[i] <= a[j]，则将a[i]放入 ；反之我们将a[j]放入，最后我们可以将排序过的数组复制到原数组中 。
模板的代码实现
这里我就将模板实现源码直接放在下面：
void merge_sort(int a[], int l, int r) { int mid = (l + r)/ 2 ; //找出我们的中点，也就是mid if (l >= r) return ; //进行判断 元素是否大于一个 merge_sort(a, l, mid) ; //递归操作 merge_sort(a, mid + 1, r) ; int k = 0 ; //k是总操作数，因为操作一次新数组下标要后移，这样可以记录我们的新数组下标 int i = l ; int j = mid+1 ; while (i <= mid && j <= r) //判断是否存在一个数组元素已全部放入 if (a[i] <= a[j]) tmp[k ++ ] = a[i ++ ] ; //对应数大小的判断 else tmp[k ++ ] = a[j ++ ] ; while (i <= mid) //对第一个数组的操作 tmp[k ++ ] = a[i ++ ] ; while (j <= r) //对第二个数组的操作 tmp[k ++ ] = a[j ++ ] ; for (i = l, j = 0; i <= r; i ++, j ++ ) { a[i] = tmp[j] ; //将数组复制到原数组 } }
例子
看到这里相信你对归并排序的实现已经有了解，那么我们举出一个实例来带你从头到尾的走一遍归并排序的过程，来看看归并排序是怎么工作的。
一般题目会给出我们一个原数组，例如这样的：
在这里为了大家观看方便我将数组下标放置元素上方 。
第一步，找中间点，分解
中间点的下标是2，那么经过我们分解得到的第一层就是这样的：
第二步 分解。
因为我们发现分开的数组都不是单独的，那么我们继续进行分层，这是我们的第二层 。
第三步 分解
对分开的区域分别进行判断，将未完全分解的数组，进行分解 ，已经成为最小单元的数组就不去进行操作了。
到这里，所有的元素都被我们拆分 。
第四步 归并
由于所有组都已经分解成只有1个元素，开始进行归并，从下向上进行归并，先比较最下一层的两组元素，14 < 27，因此将14排在27前面，由于已经没有元素，结束此次归并，如下图：
第五步 归并
继续向上一层进行归并，这一层有4个组，进行两两比较。首先，比较14、27和36：14 < 36，所以14放第一个位置，接着比较27和36，27 < 36，所以27放第二个位置，此时第一组14、27已经没有元素，于是将36填入14和27之后。接着比较12和31：12 < 31，所以12放第一个位置，由于第一组12已经没有元素，于是将31填入12之后。归并的结果如下：
第六步 归并
继续向上一层进行归并，这一组有2个组，第一组：14、27、36，第二组：12、31。同样的，取两组的第1个数比较：14 > 12，所以12放第1个位置；接着取第二组的第2个数比较：14 < 31，所以14放第2个位置；接着取第一组的第2个数比较：27 < 31，所以27放第3个位置；接着取第一组的第3个数比较：36 > 31，所以31放第4个位置；由于第二组已经没有元素，所以37自然归入第5个位置。此时，归并结束，最终数组如下。
整体流程图
所有整体的流程图就是这样的：
通过上面的细分加上这张图，可以很清晰的了解到归并排序是怎么样去进行实现的了 。
实战
第一题 归并排序
题目：
给定你一个长度为 n 的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼1091∼109 范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤100000
输入样例：
5 3 1 2 4 5
输出样例：
1 2 3 4 5
思路：
大家通过读题就可以看的出来，这道题目很明显的就是在考察我们归并排序的一个基础，我们只需做好我上面提到三步就可以，第一步：输入；第二步：调用我们的模板；第三步：输出。即可
需要注意的是，我们在调用模板的时候要弄清楚我给的模板，要从主函数之中输入什么就可以了，其余就没有任何难度了 。
AC:
#include <iostream> using namespace std ; const int N = 100010 ; int a[N], temp[N] ; void merge_sort(int a[], int l, int r) //模板 { int mid = (l+r)/2 ; if(l>=r) return ; merge_sort(a, l, mid) ; merge_sort(a, mid+1, r) ; int sum = l, i = l, j = mid+1 ; while(i<=mid && j<=r) { if(a[i] <= a[j]) temp[sum++] = a[i++] ; else temp[sum++] = a[j++] ; } while(i<=mid) temp[sum++] = a[i++] ; while(j<=r) temp[sum++] = a[j++] ; for(int i=l; i<=r; i++) { a[i] = temp[i] ; } } int main() { int n ; //输入 cin >> n ; for(int i=0; i<n; i++) { cin >> a[i] ; } merge_sort(a,0,n-1) ; //调用模板 for(int i=0; i<n; i++) //输出 { cout << a[i] << " " ; } return 0 ; }
第二题 逆序对数量
题目：
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。
输入样例：
6 2 3 4 5 6 1
输出样例：
5
思路：
很明显，这道题目的难度就远高于上一道题，并且通过我们读题并不能发现这道题想要考察我们什么，既然我将这道题目放在这里了，那么这道题就是考察的归并排序，但是在比赛的时候，我们要自己通过题目去判断这道题到底考察的什么，所有我们就来分析以下这个题目 。
我们在上面学习归并排序的时候讲到，归并操作是将要将两个有序数组合并为一个有序数组的，那么我们观察将数组一分为二后的两个部分，很明显这两个部分都是有序的，而且第二部分数组对应的数组下标肯定是大于第一部分所对应的数组下标的，有了这两个规律我们进行假设：如果存在a[i]>a[j],首先由于j是在第二部分，那么j大于第一部分的所有下标，其次a[i]>a[j],这也就满足了我们题目中所提到了一对逆序数的条件了，而且两个部分的数组均是递增的，那么第一部分a[i]后面的数也都不会比a[i]小，那么第一部分a[i]以及a[i]后面的数字都可以作为a[j]的逆序对数，这样看来我们a[j]在第一部分的逆序对数量就是：mid-i+1 了。
这个时候肯定会有朋友问，这种情况虽然成立，但不一定唯一啊，也有可能会出现其他情况啊，这应该怎么办啊？
这时我们先从整体数组开始观察，我们将数组中的逆序对数分为三种情况：均在mid点的左边，均在mid点的右边，一左一右 。在图中我也以红黄蓝三种情况去进行了表示。
我们正常思考，如果我们要算逆序对的数量，肯定要将红黄蓝三种情况相加。那么逆序对数量=红色情况+黄色情况+蓝色情况了。
红色情况 = merge_sort(L,mid) ;
蓝色情况 = merge_sort(mid+1,R) ;
黄色情况 = mid-i+1 ;
看到这里你是不是觉得问题已经解决了，然而并没有，看上面三种情况看似都列出的公式，但是只有黄色情况的公式我们在开头已经进行的论证，是完全正确的，红色和蓝色的情况并不一定正确，那么为什么红色与蓝色的数量可以由merge_sort(L,mid)和merge_sort(mid+1,R)去表示呢也就是我们为什么要使用归并排序去进行计算呢？
下面这个图就可以很好的展现出红黄蓝三种情况的组成以及在此基础上去再分解为红黄蓝三种情况的展示 。
我们来分析一下，我们索要的结果由红黄蓝三种部分所组成，而我们红色和蓝色的部分又可以分成由红黄蓝所组成的三种情况，所有我们从下往上去看，我们将数组元素分成只有单个元素的时候，这个时候红色和蓝色的情况就不会存在了，因为mid两边不会存在一个以上的数去让给他们进行比较，所以就不会存在红色和蓝色的情况了，这时我们上推一层就会清楚的发现倒数第二层的红色或蓝色情况也都是由倒数第一层的黄色情况所组成，这样我们依次的去向上推进，就会发现，看似是红+黄+蓝的组合，但其实他的本质确实黄色一种情况 。
那我们为什么要使用归并排序呢，归并排序就可以很好的满足求逆序对数这一特点，我们以及学习了如何去归并排序，归并排序是要将一个数组分解为单个单元之后再去合并的，那么在分解成单个单元之后，我们就不会出现红色和蓝色的情况了，也就是我们在进行归并排序的过程中，只需去考虑黄色的数量，并将黄色的数量逐层累加，这样我们最后就可以得到逆序对数。也正是归并排序有着将数组分为最小单元并且从下向上合二为一的这种性质，所以我们在计算逆序对数时才会选用这种办法。
正是因为逆序对数其数量最后本质上都是黄色情况的总和，所以这也正是我在刚开始就将黄色部分的计算方法做出讲解的原因。 这也就很好的解决一开始去怀疑会出现其他情况的疑问。
AC：
代码部分我们还是使用其模板，但是我们要在模板的基础上去根据我们题目的要求做出一些小小的变更即可，其变更详细内容就见代码区的注释就好。
#include <iostream> using namespace std ; typedef long long LL ; const int N = 100010 ; int a[N] ; int tmp[N] ; LL res = 0 ; //res 就是逆序对数量 LL merge_sort(int a[], int l, int r) //因为这里我们最后要返回逆序对数量，所有我们在这里设置了long long类型 { int mid = l+r>>1 ; //找中间点 if(l>=r) return 0 ; //判断元素个数 res = merge_sort(a, l, mid) + merge_sort(a, mid+1, r) ; //红色和蓝色数量，本质在上面已经讲清楚了 int k=0 , i=l, j=mid+1 ; while(i<=mid && j<=r) { if(a[i] <= a[j]) tmp[k++] = a[i++] ; else { res += mid-i+1 ; //计算我们所说的黄色情况 tmp[k++] = a[j++] ; } } while(i<=mid) tmp[k++] = a[i++] ; while(j<=r) tmp[k++] = a[j++] ; for(int i=l, j=0; i<=r; i++, j++) { a[i] = tmp[j] ; } return res ; } int main() { int n ; //输入 cin >> n ; for(int i=0; i<n; i++) cin >> a[i] ; merge_sort(a,0,n-1) ; //调用模板 cout << res << endl ; //输出 return 0 ; }
结尾
到了这里，我们今天的内容讲解也就结束了，希望大家啊都可以很好的学到这些算法知识，学习算法是日积月累的，所以不要心急，每天学一点，到最后你一定会成功的。对啦，还要记得复习今天所讲的内容噢，特别时模板，要多去熟悉几遍。
最后，如果大家喜欢我讲的内容，还请高抬贵手赞一个，如果你想跟我继续学下去，还请关注本人这个系列，我会不定期为大家更新一些算法的知识讲解以及题目讲解，如果大家有什么想学习的知识，可以留言在评论区内，我会尽快为大家出相关的文章。
