归并排序详解

yedalong

·

2024-09-26 13:35:56

·

算法·理论

什么是归并排序

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

归并排序的思路

下面将由我带大家跑一遍归并排序。\

假设一开始有个无序数组：5 4 6 9 8，

我们的目的是将这个数组从小到大排序。\

我们将它分成两个部分\

\

继续细分下去，直到全为单个数字（单个数字也是一个有序数列）\

分完后，就要开始合并了\

合并过程是最重要的，规则如下：\

对于两个有序的序列合并，因为是有序的，所以我们只需比较两个序列的第一个元素，取最小值放到一个数组里维护，再将这数删除，直到这个数组维护完两个区间，再将这个有序的数组在原封不动的复制到这两个区间上。\

对于这个数列排序过程如下：\

\

最后就排好序啦！

归并排序的模板

#include

using namespace std;

int n,arr[10005];

void merge(int l,int mid,int r){//合并操作，重点

queue q;//此队列用于维护 l 到 r 区间内的有序数列，可以用数组代替

int left=l;//此变量用于存左半区的第一个数的下标

int right=mid+1;//此变量用于存右半区的第一个数的下标

while(left<=mid&&right<=r){//如果左半区和右半区的数都还没取完

if(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<

return 0;

}

例题

怎没样？学废会了吗？赶紧实战一下吧！\

P1908 逆序对\

P1774 最接近神的人\

B3874 [GESP202309 六级] 小杨的握手问题\

P1309 [NOIP 2011 普及组] 瑞士轮