SolitudeAlma

今天我们来介绍一下归并排序

那么什么是归并排序呢？🤔🤔🤔

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

也可以看看动态图😮😮😮

归并排序也和快速排序一样利用分治法来解决问题，同样它也采用了双指针算法（排序的时候），首先将一个有序或者无序的序列按中间索引（下标）分成两个部分，然后再将这两个部分继续分，直到区间长度为1。一个长度为n的区间一共需要分 $log_2n$ 次才能将区间分完。分完区间后就是对区间进行排序，然后合并区间即可。

因为一共需要分 $log_2n$ 次区间，所以归并排序的时间复杂度为 $O(nlogn)$

我们先来看看归并排序的模板👇👇👇

void merge_sort(int q[] , int l , int r)
{
    if(l >= r) return;//区间只有一个数的时候停止递归

    int mid = l + r >> 1;//划分区间
    merge_sort(q , l , mid) , merge_sort(q , mid + 1 , r);//递归划分左右区间

    int i = l , j = mid + 1 ,  k = 0 , temp[r - l + 1];//i为左区间的指针，j为右区间的指针，k为排序的第几个数，temp数组用于合并区间时临时存储,temp也可以直接开一个和q一样大的全局变量，看个人喜好

    //两个区间的数进行比较，小的或者相等的数将左区间的数放入temp，否则右区间放入
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) temp[k ++] = q[i ++];
        else temp[k ++] = q[j ++];
    }

    // 因为存在还没比较完就有一个区间已经没有数了，所以将剩余的数全部放在temp后，一下while只有一个会执行
    while(i <= mid) temp[k ++] = q[i ++];
    while(j <= r) temp[k ++] = q[j ++];

    for(int i = l , j = 0; i <= r; ++ i , ++ j) q[i] = temp[j];//将temp数组更新到q数组中，q即为排序后的数组
}

归并排序的三个步骤

确定分界点 mid = l + r >> 1;

递归排序左右区间

归并区间❤️❤️❤️

首先将区间一直划分，直到区间长度为1，接着排序左右区间，最后合并区间。
合并区间之前，区间一定是有序的

从左区间开始排序，此时区间中只有一个3，递归停止（只有一个元素不需要排序），排完后轮到右区间，此时区间中也是只有一个数，不需要排序，递归停止。跳回到上一层递归，然后排序3和1，因为本层递归将区间用mid划分了，也就是意义上的左右区间，形式上还是在同一个数组中，因为 q[i] = 3 是大于 q[j] = 1 的，所以将 q[j] 放入temp数组中，要注意这里的k++，++的位置意味着如果它在一个表达式中的话运算顺序是不一样的，除非它单独为一条语句，那它的位置在哪都一样，如果不能理解的话，单独拎出来自增也是可以的。然后此时 i > mid ，所以while循环停止，接着把未比较完的数放进temp中，这样就合并完第一个区间了，然后更新q数组的前两个位置，如此往复就能把数组排序完了。

老规矩，自己手动模拟的话能更快的理解。

一些细节

k++和++k在单独的一个语句中并没有什么区别，k都会自增。但是如果在一个表达式中的话就不一样了，比如temp[k ++] = q[i ++],在这里是先用k和i的值，然后k和i再加1。我是这么记的，谁在前面谁先执行，即k++是先赋值后加1，++k是先加1后赋值

emmm,好像没有了，有的时候再加上吧

这个算法的难点在于合并区间，必定会有一个区间先比较完，然后得把剩余的所有数全部放入temp数组中，模板中的方法就很不错

又到了呈上例题的时候🤣🤣🤣

AcWing 787. 归并排序

题目描述

给定你一个长度为n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

$1≤n≤100000$

输入样例：

$5$
$3 1 2 4 5$

输出样例：

$1 2 3 4 5$

C++代码

#include <cstdio>

using namespace std;

const int N = 100010;

int n;
int a[N];

void merge_sort(int q[] , int l , int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;
    
    merge_sort(q , l , mid) , merge_sort(q, mid + 1 , r);

    int i = l , j = mid + 1 ,  k = 0 , temp[r - l + 1];
    while(i <= mid && j <= r)
    {
        if(q[i] <= q[j]) temp[k ++] = q[i ++];
        else temp[k ++] = q[j ++];
    }

    while(i <= mid) temp[k ++] = q[i ++];
    while(j <= r) temp[k ++] = q[j ++];

    for(int i = l , j = 0; i <= r; ++ i , ++ j) q[i] = temp[j];
}

int main()
{
    scanf("%d" , &n);

    for(int i = 0; i < n; ++ i) scanf("%d" , &a[i]);

    merge_sort(a , 0 , n - 1);

    for(int i = 0; i < n; ++ i) printf("%d " , a[i]);

    return 0;
}

以上就是我对归并算法的一些理解，如有错误的地方请大佬们指出。🤺🤺🤺

对归并排序的一些理解