归并排序详解

· · 算法·理论

什么是归并排序

归并排序是由冯・诺伊曼发明的，是建立在归并操作之上的一种高效的排序方式。它的速度仅次于快速排序，时间复杂度 O(n \log n)，空间复杂度 O(n)，是稳定的排序算法。归并排序的运用领域非常广泛，最常见的就是解决逆序对的问题。可以说，归并排序是非常优秀的。

归并排序的思路

下面将由我带大家跑一遍归并排序。\ 假设一开始有个无序数组：5 4 6 9 8， 我们的目的是将这个数组从小到大排序。\ 我们将它分成两个部分\ \ 继续细分下去，直到全为单个数字（单个数字也是一个有序数列）\ 分完后，就要开始合并了\ 合并过程是最重要的，规则如下：\ 对于两个有序的序列合并，因为是有序的，所以我们只需比较两个序列的第一个元素，取最小值放到一个数组里维护，再将这数删除，直到这个数组维护完两个区间，再将这个有序的数组在原封不动的复制到这两个区间上。\ 对于这个数列排序过程如下：\ \ 最后就排好序啦！

归并排序的模板

#include <bits/stdc++.h>
using namespace std;
int n,arr[10005];
void merge(int l,int mid,int r){//合并操作，重点 
    queue<int> q;//此队列用于维护 l 到 r 区间内的有序数列，可以用数组代替 
    int left=l;//此变量用于存左半区的第一个数的下标 
    int right=mid+1;//此变量用于存右半区的第一个数的下标 
    while(left<=mid&&right<=r){//如果左半区和右半区的数都还没取完 
        if(arr[left]<arr[right]) q.push(arr[left++]);//如果左半区的第一个数比右半区的第一个数更小，将左半区的第一个数放入队列维护 
        else q.push(arr[right++]);////如果右半区的第一个数比左半区的第一个数更小，将右半区的第一个数放入队列维护 
    }
    while(left<=mid) q.push(arr[left++]);//将左半区剩余数直接取空 
    while(right<=r) q.push(arr[right++]);//将右半区剩余数直接取空 
    for(int i = l;i<=r;i++) arr[i]=q.front(),q.pop();//将维护好的有序队列复制到 l 到 r 区间内的数组里 
} 
void Merge_sort(int left,int right){//归并排序函数主体 
    if(left!=right){//如果不为一个数，递归分治 
        int mid=(left+right)/2;//将 left 到 right 区间分成两半 
        Merge_sort(left,mid);//左半区 
        Merge_sort(mid+1,right);//右半区 
        merge(left,mid,right);//合并 
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>arr[i];//输入 
    Merge_sort(1,n);//归并 
    for(int i = 1;i<=n;i++) cout<<arr[i]<<' ';//输出
    return 0;
}

例题

怎没样？学废会了吗？赶紧实战一下吧！\ P1908 逆序对\ P1774 最接近神的人\ B3874 [GESP202309 六级] 小杨的握手问题\ P1309 [NOIP 2011 普及组] 瑞士轮