【数据结构与算法】归并排序：从理论到实践的深度剖析

一、引言

在众多排序算法中，归并排序以其独特的分而治之策略、稳定的排序结果以及相对较高的效率脱颖而出，成为了许多场合下的首选算法。 归并排序通过递归地将数据集分成越来越小的半子表，直至每个子表只包含一个数据元素（此时认为该子表已排序），然后将这些有序的半子表合并成一个大的有序表，以此实现整个数据集的排序。这一过程不仅展示了算法设计的精妙之处，也体现了计算机科学中递归与分治思想的重要应用。 本文旨在深入探讨归并排序的各个方面，从原理剖析到具体实现，再到性能优化与实际应用，力求为读者呈现一个全面而深入的归并排序知识体系。 通过本文的学习，读者将能够深入理解归并排序的核心思想、掌握其实现方法，并能够在实际应用中灵活运用这一强大的排序工具。同时，本文还将对归并排序的优缺点进行客观分析，帮助读者在不同场景下选择合适的排序算法，实现最优的数据处理效果。

二、归并排序的基本原理

归并排序（Merge Sort）是一种分而治之的排序算法。它将数组分成两半，对每半部分递归地应用归并排序，然后将结果合并成一个有序数组。归并排序的关键在于合并两个已排序的数组段

三、实现思路

注意： 因为归并排序在合并过程中需要一个与待排序数组大小相同的临时数组来存储合并的结果。 所以直接在进入函数之后一次申请一个同样大小的空间，免去多次动态申请空间和释放的消耗 主调函数只完成空间申请和释放，以及中间的调用子函数 将归并排序的核心代码放在子函数完成

子函数的任务（归并的核心）：

🍃1. 分解

• 将当前区间一分为二，即找到中间位置mid = (left + right) / 2
• 递归地对左半部分left...mid进行归并排序。
• 递归地对右半部分mid+1...right进行归并排序。

🍃2. 解决

• 在归并排序中，“解决”步骤实际上是在递归调用中隐式完成的，即通过递归调用自身来实现对左右子数组的排序。
• 当递归调用达到基本情况（即子数组只有一个元素或为空时），由于一个元素的数组自然是有序的，因此不需要进行任何操作，递归开始返回。

🍃3. 合并（以升序为例）：核心代码

• 使用两个变量i和j，分别指向左半部分和右半部分的起始位置。
• 比较左半部分和右半部分当前指针所指的元素，将较小的元素先存入temp数组，并移动对应的变量。
• 重复上述步骤，直到左半部分或右半部分的所有元素都被复制到temp数组中。
• 将左半部分或右半部分中剩余的元素（一定是某部分的元素先复制完成）直接复制到temp数组的末尾。
• 将temp数组中的元素复制回原数组，以完成合并过程。

四、C语言实现代码

// 归并排序递归实现升序
void Merge1(int left,int right,int* a,int* tmp)//归并排序子函数
{
	if (left >= right)//区间只有一个元素或不存在时不需要归并
		return;
	int mid = (left + right) / 2;//取得下标中间值
	Merge1(left, mid, a, tmp);//递归左区间
	Merge1(mid + 1, right, a, tmp);//递归右区间

	int begin1 = left,end1 = mid;//左区间范围
	int begin2 = mid + 1,end2 = right;//右区间范围
	int begin = left;
	while (begin1 <= end1 && begin2 <= end2)//二路归并
	{
		if (a[begin1] < a[begin2])
			tmp[begin] = a[begin1++];
		else
			tmp[begin] = a[begin2++];
		begin++;
	}
	//判断哪个区间元素没有遍历完，直接搬下来
	while (begin1 <= end1)
		tmp[begin++] = a[begin1++];
	while (begin2 <= end2)
		tmp[begin++] = a[begin2++];

	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
	//将归并和排序之后的数据拷贝至原数组
}
void MergeSort1(int* a, int n)//归并排序主调函数
{
	int* tmp = (int*)malloc(sizeof(int) * n);//申请临时数组
	if (tmp == NULL)
	{
		perror("Merge malloc\n");
		return;
	}
	Merge1(0, n - 1, a, tmp);//调用归并函数
	free(tmp);//排序完成释放空间
	tmp = NULL;
}

// 归并排序递归实现降序
void Merge2(int left, int right, int* a, int* tmp)//归并排序子函数
{
	if (left >= right)//区间只有一个元素或不存在时不需要归并
		return;
	int mid = (left + right) / 2;//取得下标中间值
	Merge2(left, mid, a, tmp);//递归左区间
	Merge2(mid + 1, right, a, tmp);//递归右区间

	int begin1 = left, end1 = mid;//左区间范围
	int begin2 = mid + 1, end2 = right;//右区间范围
	int begin = left;
	while (begin1 <= end1 && begin2 <= end2)//二路归并
	{
		if (a[begin1] > a[begin2])
			tmp[begin] = a[begin1++];
		else
			tmp[begin] = a[begin2++];
		begin++;
	}
	//判断哪个区间元素没有遍历完，直接搬下来
	while (begin1 <= end1)
		tmp[begin++] = a[begin1++];
	while (begin2 <= end2)
		tmp[begin++] = a[begin2++];

	memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));
	//将归并和排序之后的数据拷贝至原数组
}
void MergeSort2(int* a, int n)//归并排序主调函数
{
	int* tmp = (int*)malloc(sizeof(int) * n);//申请临时数组
	if (tmp == NULL)
	{
		perror("Merge malloc\n");
		return;
	}
	Merge2(0, n - 1, a, tmp);//调用归并函数
	free(tmp);//排序完成释放空间
	tmp = NULL;
}

五、归并排序改造：非递归实现

归并排序的非递归实现（也称为迭代实现）主要依赖于循环而非递归调用来分解和合并数组。与递归实现相比，非递归实现避免了递归调用栈的开销，但需要更复杂的索引和边界处理。

下面是详细的实现思路：

1. 初始化：
   • 分配一个与原始数组a相同大小的临时数组tmp，用于合并过程中暂存数据。
   • 定义一个变量gap，初始化为1，表示当前合并操作中每个子数组段的长度。
2. 迭代合并：
   • 通过一个外层while循环，不断增大gap的值（每次循环后gap *= 2），直到gap达到或超过数组长度n，此时整个数组已经合并为一个有序的大段，循环结束。
   • 在每次gap增大的过程中，内层for循环遍历数组，步长为2 * gap，这意味着每次处理的是两个相邻的、长度为gap的子数组段。
3. 处理子数组段：
   • 对于每一对相邻的子数组段（左区间和右区间），分别计算出它们的起始和结束位置（begin1, end1, begin2, end2）。
   • 注意处理边界情况：如果右区间的起始位置begin2越界，说明没有足够的右区间可以合并，直接跳出内层循环。如果右区间的结束位置end2越界，则将其调整为数组的最后一个元素的位置。
4. 合并子数组段（这一部分核心代码和递归实现是相同的）：
   • 使用两个指针（begin1和begin2）分别遍历左区间和右区间，并将较小的元素复制到临时数组tmp中。同时，使用一个指针begin来追踪tmp中当前的位置。
   • 当其中一个区间遍历完成后，将另一个区间中剩余的元素直接复制到tmp的末尾。
5. 复制回原数组：
   • 将合并后存储在tmp中的有序子数组段复制回原数组a中对应的位置。这里使用memcpy函数进行复制，复制的长度是end2 - i + 1，即合并后子数组段的长度。注意，这里的i是当前合并的子数组段的起始位置。
6. 清理资源：
   • 当整个数组排序完成后，释放临时数组tmp所占用的内存资源。

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);//申请临时数组
	if (tmp == NULL)
	{
		perror("Merge malloc\n");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;//左区间范围
			int begin2 = i + gap, end2 = i + 2 * gap - 1;//右区间范围
			int begin = i;

			if (begin2 >= n)//如果右区间初始位置越界了，说明右区间不存在
				break;
			if (end2 >= n)//如果右区间初始位置未越界，结束位置越界了，调整结束位置至数组尾部
				end2 = n - 1;
			while (begin1 <= end1 && begin2 <= end2)//二路归并
			{
				if (a[begin1] < a[begin2])
					tmp[begin] = a[begin1++];
				else
					tmp[begin] = a[begin2++];
				begin++;
			}
			//判断哪个区间元素没有遍历完，直接搬下来
			while (begin1 <= end1)
				tmp[begin++] = a[begin1++];
			while (begin2 <= end2)
				tmp[begin++] = a[begin2++];

			memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));

		}
		gap *= 2;

	}
	free(tmp);
	tmp = NULL;
}

六、性能分析

时间复杂度：O(n log n) 归并排序的时间复杂度在最好情况、最坏情况和平均情况下均为O(n log n)，其中n是待排序元素的数量。这是因为归并排序采用分治策略，将问题分解成两个子问题，然后递归解决子问题，最后将子问题的解合并得到原问题的解。这个过程中，每次分解都会将问题规模减半，因此分解的层数为log n，而每层合并的时间复杂度为O(n)，所以总的时间复杂度为O(n log n)。

• 最好情况：当输入数组已经是有序的时，归并排序仍然需要进行log n次分割，但每次合并操作会非常快，因为两个子数组已经是有序的，所以只需要进行少量的比较和移动操作。然而，由于分割过程的时间复杂度是O(log n)，因此最好情况下的时间复杂度仍然是O(n log n)。不过，需要注意的是，在实际操作中，由于减少了合并过程中的比较次数，最好情况下的实际执行时间可能会比平均情况稍快一些。
• 最坏情况：当输入数组是完全逆序的时，归并排序的分割过程与最好情况相同，但每次合并操作都需要进行大量的比较和移动操作，因为需要将一个子数组的最大元素与另一个子数组的所有元素进行比较并移动。然而，即使在最坏情况下，归并排序的时间复杂度仍然是O(n log n)。
• 平均情况：对于随机排列的输入数组，归并排序的时间复杂度同样是O(n log n)。这是因为尽管某些合并操作可能比最好情况下的时间复杂度高，但平均来看，每个元素仍然只需要比较和移动log n次。

空间复杂度：O(n) 归并排序的空间复杂度为O(n)，其中n是待排序元素的数量。这是因为归并排序在合并过程中需要一个与待排序数组大小相同的临时数组来存储合并的结果。此外，如果采用递归实现归并排序，还需要额外的栈空间来保存递归调用过程中的中间状态。然而，由于递归调用的深度为log n（与分割的层数相同），因此栈空间的使用量相对较小，通常可以忽略不计。 需要注意的是，虽然归并排序的空间复杂度为O(n)，但在实际应用中，如果数据量非常大且内存资源有限，那么归并排序可能会受到内存使用的限制。在这种情况下，可以考虑使用外部归并排序算法，该算法可以将数据分块读入内存进行排序，并逐块合并结果。

稳定性：稳定 归并排序是一种稳定的排序算法。在归并排序的合并过程中，如果两个相等的元素分别来自左右两个子数组，并且左子数组中的元素在右子数组中的元素之前出现，那么在合并后的数组中这两个相等的元素也会保持原来的相对顺序。这种稳定性在某些应用场景中非常重要，例如需要保持记录原始顺序的排序操作。

七、应用场景

归并排序适用于多种场景，包括但不限于：

• 大数据集排序：由于归并排序的时间复杂度为O(n log n)，因此它非常适合处理大规模数据的排序问题。
• 外部排序：当数据量太大无法全部加载到内存中时，可以使用外部归并排序算法对数据进行分块排序和合并。
• 并发编程：在多线程或分布式系统中，归并排序可以很容易地并行化。每个线程或进程可以独立地排序数据的一部分，然后合并结果。
• 数据库系统：数据库管理系统中的排序操作经常使用归并排序来确保数据的稳定性和正确性。
• 算法教学：归并排序是计算机科学教育中常用的教学示例之一，用于讲解分治策略和递归思想。

综上所述，归并排序以其稳定的排序结果、较高的排序效率和广泛的应用场景而备受青睐。然而，在实际应用中也需要根据具体的数据特性和资源限制来选择合适的排序算法。