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

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

百度百科是这么说的:归并排序(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即为排序后的数组
}

归并排序的三个步骤

  1. 确定分界点 mid = l + r >> 1;
  2. 递归排序左右区间
  3. 归并区间❤️❤️❤️

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

划分过程

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

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

一些细节

kk在单独的一个语句中并没有什么区别,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;
}

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

Q.E.D.


都懂一点,不是很懂的小捞仔