Garbage fish

主题

00:00:00
Garbage fish2023-08-09杂类算法
844
3.5m

归并排序 笔记 ​

一. 为什么选用归并排序 ​

归并排序，是众多排序算法的其中一种。归并排序的时间复杂度是一般排序算法里最小的，达到了 O(nlog⁡n)。

为什么不用 sort？同样也是 O(nlog⁡n)。

因为 sort 很有可能 （极小可能） 被卡到 O(n2)（即当序列本身有序时），因此选用归并排序更为保险麻烦。

二、归并排序的原理 ​

以下以按小到大排序来举例。

1. 拆 ​

将序列分成两半，再将分成的序列分成两半，直到每个序列只剩 1 个元素为止。

2. 选 ​

两两选择拆分出来的小序列，比较左序列和右序列的头，按小到大加入新序列。

3. 合 ​

此时，新的左序列有序了，新的右序列通过类似操作也有序了，再将它们用相同的步骤组合起来……我们就得到了一个有序的序列。

演示图如下所示：

在这种排序算法中，选的时间复杂度是 O(n)，而拆的复杂度则是 O(log⁡n)，因此，归并排序的时间复杂度是 O(nlog⁡n)。

三、归并排序代码实现 ​

1. 拆 ​

通常采用函数来划分，然后用一个新的数组来存合并后的结果：

cpp
if(L>=R)return;//如果这一段序列左端点等于右端点，说明只剩一个数，无需进行操作，直接返回。
int mid=(L+R)>>1;//取中间点。
merge(d,L,mid),merge(d,mid+1,R);//继续枚举接下来两个区间，其中 d 是数组。

2. 选 ​

这一步是归并排序的重点，需用两个下标，比较是左序列当前下标的小，还是右序列当前下标的小，将较小者放入新序列中，继续进行下一轮比较。

需要注意的是，当比较完之后，可能出现左序列或右序列还有几个数因为比其它数都要大，没加入到新序列中。这时候需要另外将他们加入序列中。

cpp
int li=L,ri=mid+1,ti=L;//li, ri 表示两个序列当前枚举的下标。ti 是新序列的下标，tmp 是新序列。
while(li<=mid and ri<=R){
	if(d[li]<=d[ri])tmp[ti++]=d[li++];//大到小用 ">=" , 小到大用 "<=" . 
	else tmp[ti++]=d[ri++];
}
while(li<=mid)tmp[ti++]=d[li++];//将两个序列剩余的部分加入至新序列末尾。
while(ri<=R)tmp[ti++]=d[ri++];

3. 合 ​

这一部分没啥好说的，就是将新序列的结果放入回旧序列中：

cpp
for(int i=L;i<=R;i++){
	d[i]=tmp[i];
}

4. 模板题代码 ​

平台网址
洛谷https://www.luogu.com.cn/problem/P1177

AC 代码如下：

cpp
#include <cstdio>
using namespace std;
int n,a[100010],tmp[100010];
void merge(int d[],int L,int R){
	if(L>=R)return;
	int mid=(L+R)>>1;
	merge(d,L,mid),merge(d,mid+1,R);
	int li=L,ri=mid+1,ti=L;
	while(li<=mid and ri<=R){
		if(d[li]<=d[ri])tmp[ti++]=d[li++];	//大到小用 ">=" , 小到大用 "<=" . 
		else tmp[ti++]=d[ri++];
	}
	while(li<=mid)tmp[ti++]=d[li++];
	while(ri<=R)tmp[ti++]=d[ri++];
	for(int i=L;i<=R;i++){
		d[i]=tmp[i];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	merge(a,1,n);
	for(int i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
	return 0;
}
最近更新