【面试必备】排序算法——归并排序

排序算法是在我们求职面试的时候有很大的概率会被提及，因为不管是在工程类方向中还是在研究类方向中，排序算法的思想都有广泛的应用。
下面，我就来大致的介绍一下各种面试中常见的排序算法的基本思想和相关的实现，希望对你有所帮助。
以下的排序思想都会基于这个序列21,12,34,67,25,46,52,19来进行讲解，同时配上适当的图解和代码以及代码注释一起讲解。请放心食用。最后的序列都会按照从小到大的顺序进行排列，大家可以自己修改代码，使得序列按照从大到小的顺序排列，以此来检验自己的学习成果。

归并排序

归并排序也称合并排序。
大致思想
- 将整个序列看成一个大区间，然后不断地将区间基于区间中点一分为二，最后，得到区间地长度为1的小区间。如上面的序列，一共有8个元素，我们初始的区间为 $[0,7]$ ,进行一次二分变成了两个区间，分别为 $[0,3],[4,7]$ ，然后继续将区间 $[0,3],[4,7]$ 进行二分得到 $[0,1],[2,3],[4,5],[6,7]$ ,最后，再对这些区间进行二分得到 $[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7]$ 。其实到了这里，大部分同学应该也感受到了这个过程有点像二叉树的建立过程。所以，其实这个过程可以看作是把这个序列抽象成了一棵二叉树。（如下图）
- 当我们不断细分到最小的区间的时候，我们就可以开始进行合并了了。对于有相同的父节点的子节点，我们可以保证在合并前，这两个子节点内部一定是有序的（因为我们最起始的状态就是区间长度为1的区间，这个肯定是有序的，后面都是基于已经合并的区间进行处理的）。所以我们建立一个缓冲区，将这两个内部有序的子区间合并成一个有序的大区间。如此不断进行递归，最后，我们就可以得到一个完成而有序的大区间了。
- 排序算法完成。
图解分析
- 上面的图解圆圈标号表示的是不断向下拆分的时候的先后顺序，红色标号标明的是进行区间合并的先后顺序。
代码实现思路
- 初始化一个序列A，得到区间的左右端点 $left，right$ 。
- 找出当前序列的区间中点 $mid$ ，基于区间中点将区间一分为二，得到的两个区间 $[left,mid],[mid+1,right]$ 继续执行一分为二的操作，知道区间 $left$ 等于 $right$ 。
- 最后，将两个内部有序的小区间合并成一个有序的大区间。具体的实现是建立一个缓冲区，给两个小区间一个游标idx1，idx2，然后不断比较两个游标的对应的元素的大小，如果 $A[idx1]<A[idx2]$ ,那么就 $idx1++$ ,否则就 $idx2++$ 。最后肯定有一个游标遍历完了整个区间，而另一个没有遍历完，将没有遍历完的区间的部分都追加到缓冲区里面即可。最后缓冲区里面的数据都是有序的了，我们将缓冲区对应的下标的元素放到序列A的对应的下标即可。那么，序列A的这个区间的元素就都是有序的了。
代码实现

#include<iostream>
#define LEN 8
using namespace std;
void print(int a[]){
    for(int i=0;i<LEN;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
/**
 * @brief 合并函数
 * 
 * @param a 需要排序的数组
 * @param left1 左区间的左端点
 * @param right1 左区间的右端点
 * @param left2 右区间的左端点
 * @param right2 右区间的右端点
 */
void merge(int a[],int left1,int right1,int left2,int right2){
    int buff[LEN]; // 定义好一个缓冲区数组
    int idx1=left1,idx2=left2,idx=0; // 定义好两个区间的初始游标
    // 不断地进行比较，找到两个区间地当前的更小值，放到缓冲区里面
    while(idx1<=right1&&idx2<=right2){
        // 左边区间的当前值小于右边区间的当前值
        if(a[idx1]<a[idx2]){
            buff[idx++]=a[idx1];
            ++idx1;
        }else{
            // 右边区间的当前值小于等于左边区间的当前值
            buff[idx++]=a[idx2];
            ++idx2;
        }
    }
    // 将区间剩余的部分都追加到缓冲区里面
    while(idx1<=right1){
        buff[idx++]=a[idx1];
        ++idx1;
    }
    while(idx2<=right2){
        buff[idx++]=a[idx2];
        ++idx2;
    }
    // 将缓冲区对应的下标元素放到序列的对应的下标
    for(int i=left1,j=0;j<idx;++i,++j){
        a[i]=buff[j];
    }
}
/**
 * @brief 归并排序函数
 * 
 * @param a 需要排序的数组
 * @param left 需要进行排序的区间左端点
 * @param right 需要进行排序的区间右端点
 */
void mergeSort(int a[],int left,int right){
    // 只有在这个区间的区间长度超过1的时候才需要继续递归
    if(left<right){
        // 找到区间的中点
        int mid=(left+right)>>1;
        // 递归处理左区间
        mergeSort(a,left,mid);
        // 递归处理右区间
        mergeSort(a,mid+1,right);
        // 上面的递归处理完之后，当前的左右区间一定是内部有序的，
        // 然后再进行一个合并操作，将两个内部有序的小区间合并成一个有序的大区间
        merge(a,left,mid,mid+1,right);
    }
}
int main(){
    int a[8]={21,12,34,67,25,46,52,19};
    mergeSort(a,0,LEN-1);
    print(a);
    return 0;
}

复杂度分析
- 时间复杂度
  - 我们已经知道，长度为 $N$ 的区间，会被分为 $logN$ 层，对于每一层，需要处理的序列次数为 $\frac{N}{2^i}$ ， $i$ 为层数。总的处理的次数为 $\frac{N}{2^0}+\frac{N}{2^1}*2+\frac{N}{2^2}*4+...$ ，一共会有 $logN$ 项，所以，总的时间复杂度为 $NlogN$ 。
- 空间复杂度
  - 在进行合并的时候，主要的空间消耗是缓冲区部分，最多的空间的消耗为缓冲区的大小为 $N$ ，所以总的空间复杂度为 $O(N)$ 。