前言&复习

今天是我们0基础算法课的第二节课，今天我想给大家分享的知识是归并排序。

首先我们先来回顾一下上次课我们所学习的内容，我们在第一节课为大家讲了快速排序，在上节课中，我们了解到快速排序是排序效率在同为O(N*logN)的几种排序方法中效率较高，然后我们才用分治的方法去实现快速排序。其中的三个步骤相信大家都还记得：确认边界点-重新调整区间-递归。之后为大家举了实例并重新顺了一遍思路，就开始进行模板的实现，模板在这里是要求大家记住的，学会了模板之后，我们在遇到排序的时候，只需在主函数中输入输出相关内容，排序的时候直接调用我们的模板就可以了。

上节课大概就讲了那么多内容，如果有什么你没有掌握或者说你还不会的知识，可以直接从这里跳转到我的上一节课中去学习：【0基础学算法】快速排序(超详细讲解+私人笔记+源码）_红颜如霜凝结了过往的博客-CSDN博客

接下来我们就开始归并排序的讲解。

知识讲解

什么是归并排序

归并排序（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] ; //将数组复制到原数组 
   } 
}