归并算法：分治而治的高效算法大揭秘（图文详解）

🎬 鸽芷咕：个人主页
?🔥 个人专栏: 《数据结构&算法》《粉丝福利》

??生活的理想，就是为了理想的生活!

---

📋 前言

归并算法是我们算法中最常见的算法之一，其思想非常巧妙。本身归并是只能归并有序数组但是当我们利用了二路归并分治法之后，就可以使用归并的思想来帮我们排序其算法性能属于第一梯队。

一、什么是归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

1.1 归并的核心思想

归并的思想大家都知道就是俩个有序数组的数据进行比较，如果 数组一的数据小 就把它插入到我们的新数组里面：

• 当一个数组比较完后直接把另一个还没比较完的有序数组数组插入到新数组就归并完了

🔥 注：归并的前提是俩个数组都是有序的。

1.2 归并排序的图文解析

那么我们无序数组想要排成有序的改怎么办，这时就有人提出了分治的思想把每个数组的数据都看为一个有序数组，在进行归并

先递归进行分割然后再利用递归返回的特性来进行，回溯归并这样就可以达成俩个有序数组合并了

二、归并排序的实现

归并的思想讲完了，以上就是归并排序的全部过程了，诶这样大家是不是理解起来更方便了，既然是归并那么必须就需要一个另一个空间来存放数据：

• 而我们需要归并的数组就是原数组所递归分割我区间每次归并完了之后在复制
• 回原数组，这样就能从归并一个数据到整个数组的数据了；

-

2.1 实现代码

好滴思路捋清楚了，代码实现就简单首先我们需要开辟一个和排序数组一模一样大的空间那么就 malloc 一个但是我们需要递归分割所以肯定不能再这个函数里面进行递归这时就需要:

• _MergeSort 来进行递归分割排序数组
• 剩下的注意好每次分割的区间和，每次归并完了复制到原数组就好了

🍸 代码演示：

void _MergeSort(int* a, int* tmp, int begin, int end)
{
	if (end <= begin)
		return;

	int mid = (begin + end) / 2;
	//[begin, mid-1] [mid, end]
	_MergeSort(a, tmp, begin, mid);
	_MergeSort(a, tmp, mid+1, end);

	//开始归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int index = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		

		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	 
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	if (tmp == NULL)
	{
		perror("malloc file");
		exit(-1);
	}

	_MergeSort(a, tmp, 0, n-1);

	free(tmp);
}

这里每次的区间都是数组的区间，只要分割好了，那么就照着思路写下去就好了

三、归并排序的总结

总体来说归并排序的性能还是非常好的采取的是拿空间换时间的概念,归并排序的思考更多的是解决在磁盘中的外排序问题。

1. 归并的缺点在于需要O(N)的空间复杂度
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

📝文章结语：

看到这里了还不给博主扣个：
?? 点赞🍹收藏 ?? 关注！
💛 💙 💜 ?? 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。