前言

上期我们介绍了选择排序的改进版—堆排序，具体分析了它的基本思想，代码的实现和算法复杂度，这期我们将讲解八大排序的最后一个—归并排序。

什么是归并排序

百度百科中说归并算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。

我自己的理解就是归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序的实现

基本思想

1 把序列分成元素个数尽量相等的两半。
2 把两半元素分别进行归并排序。
3 把两个有序数组合并成一个。

具体代码

#include <stdio.h>
int merge(int r[],int s[],int x1,int x2,int x3)    //自定义实现一次归并样序的函数
{
    int i,j,k;
    i=x1;    //第一部分的开始位置
    j=x2+1;  //第二部分的开始位置
    k=x1;
    while((i<=x2)&&(j<=x3))    //当i和j都在两个要合并的部分中时
        if(r[i]<=r[j])    //筛选两部分中较小的元素放到数组s中
        {
            s[k] = r[i];
            i++;
            k++;
        }
        else
        {
            s[k]=r[j];
            j++;
            k++;
        }
        while(i<=x2)    //将x1〜x2范围内未比较的数顺次加到数组r中
            s[k++]=r[i++];
        while(j<=x3) //将x2+l〜x3范围内未比较的数顺次加到数组r中
            s[k++]=r[j++];
    return 0;
}
int merge_sort(int r[],int s[],int m,int n)
{
    int p;
    int t[20];
    if(m==n)
        s[m]=r[m];
    else
    {
        p=(m+n)/2;
        merge_sort(r,t,m,p);    //递归调用merge_soit()函数将r[m]〜r[p]归并成有序的t[m]〜t[p]
        merge_sort(r,t,p+1,n);    //递归一调用merge_sort()函数将r[p+l]〜r[n]归并成有序的t[p+l]〜t[n]
        merge(t,s,m,p,n);    //调用函数将前两部分归并到s[m]〜s[n】*/
    }
    return 0;
}
int main()
{
    int a[11];
    int i;
    printf("请输入10个数：\n");
    for(i=1;i<=10;i++)
        scanf("%d",&a[i]);    //从键盘中输入10个数
    merge_sort(a,a,1,10);    //调用merge_sort()函数进行归并排序
    printf("排序后的顺序是：\n");
    for(i=1;i<=10;i++)
        printf("%5d",a[i]);    //输出排序后的数据
    printf("\n");
    return 0;
}

归并排序的实现原理

递归：调用自身 分治：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。比喻10只筷子不好折，分成5和5，5还不好折，再分成2和3，还觉得不好折，再分成1和1（1和2）。像这样将大问题分成一样类型的小问题，在各个击破。归并排序实现思路：把数组从中间分开（分为左，右俩部分），左边再次从中间分开分成俩部分，右边再次从中间分开分成俩部分，一直这样分下去，直到不能再分。从最底层开始一直向上有序的合并。最终完成排序。

假设我们希望从小到大排序。合并的过程主要是在两个序列的起点各设置一个指针。因为两个序列已经是分别有序的了，那我们每次只需要把两个序列中最小的元素加以比较，将其中比较小的元素加入到临时数组，然后将该指针向后移动，直到其中一个序列的指针走完整个序列为止。接着需要把另一个序列可能剩下的值都加到排序之后的序列的末尾。最后将临时数组的元素值赋值回原始数组。

这里有一点需要考虑的是，当两个序列当前指针对应的元素相等时，应该移动哪一个？虽然说移动哪一个指针都可以，但是我们一般会移动第一个序列的指针。因为这样可以保持排序的稳定性。即保持序列中相同值在排序之后顺序不变。

归并排序的难点是如何合并，实际上这是比较好理解的，但是需要写更多的代码，因为需要考虑序列为空以及把临时序列的值存回原序列的情况。快速排序的难点是如何划分，这个问题我认为相对归并的难点是比较难理解的。

另一点需要注意的是，快排是先划分过程，然后递归。归并是先递归，然后合并。看上去相反的但是实际是由于两个排序的步骤有些是不需要做任何操作的。

复杂度

空间复杂度

递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个元素的大小，所以归并排序的空间复杂度是 O(n)。

时间复杂度

归并排序的递归树，树种每层元元素的个数最多是n，也就代表着每层最多进行n次比较，而递归树最多只有log2n层，合在一起就是nlog2n了。