当前位置：首页 > article >正文

算法 -归并排序

article 2025/1/12 20:48:07

博客主页：【夜泉_ly】
本文专栏：【算法】
欢迎点赞👍收藏⭐关注❤️

在这里插入图片描述

文章目录

🔀 归并排序
- 📖 简介
- 🖼️ 示意图
- 💡 实现思路
- 💻 代码实现
- 💡 实现思路2 - 非递归
- 💻 代码实现

🔀 归并排序

📖 简介

稳定的排序
时间复杂度： $\log n)$
空间复杂度： $O (n)$ ，由于需要额外的临时数组来存储合并结果。
常用于，处理 链表排序 和 文件排序

🖼️ 示意图

$归并排序 - 示意图$
在这里插入图片描述
请添加图片描述

💡 实现思路

先来看看具体是怎么排的：
第一步：先拿到需要整理的牌，将它们摊开。
在这里插入图片描述

第二步：将这些牌分成较小的组，每组包含一张牌：
在这里插入图片描述

第三步：对相邻的两组依次进行排序：
请添加图片描述

第四步：把刚刚相邻的两组看做为一组：
在这里插入图片描述

第五步及以后：重复上面的第三步、四步：
请添加图片描述
在这里插入图片描述

最后，由于只剩一组，排序结束。
怎么样，很简单吧 ~~
现在，我们来看看我们需要做什么。
在上面，看似用了很多步，其实很多步骤是重复的。
而重复，代表着可以试试递归。
总结一下：

步骤一、分组
步骤二、合并
步骤三、判断是否结束

那么我们需要关注的是什么？

一、怎么分组
二、怎么合并
三、看看什么时候结束

展开讲讲：

void merge_sort(int* arr, int left, int right)

一、怎么分？
那必须二分，想都不用想。
至于为什么？
首先是方便，其次是方便，然后是方便，
最后是效率稍高。

	int mid = (left + right) >> 1;

二、怎么合？
把上面的图抓下来：
在这里插入图片描述

这几张，就是分完后的样子。
我这里排的是升序，
可以看见，这里的每一组也都是升序：

这样看，合并就简单了。
因为我们只需要合并两个有序序列。
而如何保证这两个序列有序？
很简单，先递归：

	merge_sort(arr, left, mid);
	merge_sort(arr, mid + 1, right);

再合并：

	vector<int> tmp(right - left + 1);
	
	int l = left, r = mid + 1, cur = 0;
	while (l <= mid && r <= right) 
		tmp[cur++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
	while (l <= mid) tmp[cur++] = arr[l++];
	while (r <= right) tmp[cur++] = arr[r++];
	
	for (int i = 0; i < cur; i++) arr[i + left] = tmp[i];

递归至最后，长度变为 1 ，此时必为有序。
而如何保证最后一层长度为 1 ？
这就需要下面一步了：
三、怎么停？
看看传参：(int* arr, int left, int right)
嗯，长度 == right - left + 1;
那么我们想让长度大于等于 1。
即，我们不想长度小于 1：

	if (left >= right) return;

把这段放在函数开头，
然后
在这里插入图片描述

💻 代码实现

void merge_sort(int* arr, int left, int right)
{
	// 递归结束条件
	if (left >= right) return;
	// 找到中间位置
	int mid = (left + right) >> 1;
	// 左右递归
	merge_sort(arr, left, mid);
	merge_sort(arr, mid + 1, right);
	// 辅助数组，存合并结果
	vector<int> tmp(right - left + 1);
	// 合并两个有序序列
	int l = left, r = mid + 1, cur = 0;
	while (l <= mid && r <= right) 
		tmp[cur++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
	while (l <= mid) tmp[cur++] = arr[l++];   // 将左侧剩余元素拷贝
	while (r <= right) tmp[cur++] = arr[r++]; // 将右侧剩余元素拷贝
	// 将合并结果拷回原数组
	for (int i = 0; i < cur; i++) arr[i + left] = tmp[i];
}

在这里插入图片描述
写的时候记得注意边界，
最好把上图红色部分画出来。
不熟的话，别只用脑子想，容易红温。

在这里插入图片描述

💡 实现思路2 - 非递归

刚刚的递归，帮我们简化了什么？
分组。
递归帮我们把组分好了。

那么非递归，我们还需要做什么？
分组。

怎么分？
为了保证每次的各组都是有序的，
最小的长度为 1 ，之后两两合并。

具体怎么做？
先把下面这个图画出来：
在这里插入图片描述
然后确定每组长度：

for (int len = 1; len < n; len *= 2) {

从一开始，每次乘二。
len < n，怎么来的？
很简单，len 是子数组的长度。
子数组是排好了的。
当 len >= n，说明数组就排好了。

之后，确定两组的左边界：

for (int left = 0; left < n - len; left += 2 * len) {

有了左边界和长度，
就可以补全图中红字部分：

在这里插入图片描述

int mid = left + len - 1, right = min(n, left + 2 * len) - 1;
int l = left, r = mid + 1;

之后的合并，就和递归一样了。

最后补充说明一下边界情况：
一、left < n - len
唔。。。n - len 是为了放溢出。
便于理解的方式是这样写：left + len < n
倒过来看，就是 left + len >= n
说明了啥？
说明右边的数组不存在！
在这里插入图片描述
因此，继续循环的条件是 left < n - len
二、right = min(n, left + 2 * len) - 1
把上面的图稍稍改造，就能明白为什么这样写了：

💻 代码实现

void merge_sort(int* arr, int n)
{
	vector<int> tmp(n);
	for (int len = 1; len < n; len *= 2)
	{
		for (int left = 0; left< n - len; left += 2 * len)
		{
			int mid = left + len - 1;
			int right = min(n, left + 2 * len) - 1;
			int l = left, r = mid + 1, cur = left;
			while (l <= mid && r <= right)
				tmp[cur++] = arr[l] <= arr[r] ? arr[l++] : arr[r++];
			while (l <= mid) tmp[cur++] = arr[l++];
			while (r <= right) tmp[cur++] = arr[r++];
			for (cur = left; cur <= right; cur++) 
				arr[cur] = tmp[cur];
		}
	}
}