「前言」文章内容是排序算法之归并排序的讲解。

归并排序

1.1 原理

归并排序是一种有效的排序算法，采用分治法（Divide and Conquer）策略。它的基本思想是将数组分成两个子数组，分别对这两个子数组进行排序，然后将排序好的子数组合并在一起。

归并排序的步骤：

  1. 分解：将数组分成两半，递归地对每个子数组进行归并排序。
  2. 解决：当子数组的大小为1时，认为它们已经排序好。
  3. 合并：将两个已排序的子数组合并成一个排序好的数组。

如图：

image-20240908145957549

动图演示：（升序）

归并排序

1.2 代码实现（C++）

  • nums: 要排序的数组。
  • left: 当前排序范围的左边界。
  • right: 当前排序范围的右边界。
  • auxiliaryArr: 辅助数组，用于存放合并后的结果。

（类似于二叉树的后序遍历）

代码如下：（升序）

// 归并排序
void MergeSort(vector<int>& nums, int left, int right, vector<int>& auxiliaryArr)
{
	if (left >= right) return;
	// 1.取中间下标
	int mid = (left + right) >> 1;
	// 2.去左区间，去右区间
	MergeSort(nums, left, mid, auxiliaryArr);
	MergeSort(nums, mid + 1, right, auxiliaryArr);
	// 3.合并两个有序数组
	int cur1 = left, cur2 = mid + 1, i = left;
	while (cur1 <= mid && cur2 <= right)
	{
		if (nums[cur1] < nums[cur2])
		{
			auxiliaryArr[i++] = nums[cur1++];
		}
		else
		{
			auxiliaryArr[i++] = nums[cur2++];
		}
	}
    // 如果左半部分还有剩余元素，直接将它们复制到auxiliaryArr中
	while (cur1 <= mid) auxiliaryArr[i++] = nums[cur1++];
    // 同理右半部分
	while (cur2 <= right) auxiliaryArr[i++] = nums[cur2++];
	// 4.还原数组 -- 把auxiliaryArr中排序好的数拷贝到nums数组
	for (int j = left; j <= right; ++j)
	{
		nums[j] = auxiliaryArr[j];
	}
}

1.3 非递归实现

归并排序的非递归实现可以不借助栈、队列之类的数据结构就可以完成。

只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序。

例如：gap首先从1开始每两个进行合并，gap=2了就开始两个两个（四个）合并，gap=4了就开始四个四个（8个）合并，直到数组有序。

image-20240908211402899

极端情况：

情况一：当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不够gap个，这时我们需要在合并序列时，对第二个小区间的边界进行控制。

在这里插入图片描述

情况二：当最后一个小组进行合并时，第二个小区间不存在，此时便不需要对该小组进行合并。

在这里插入图片描述

情况三：当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间的元素个数不够gap个，此时也不需要对该小组进行合并。（与情况二归为一类）

代码如下：（升序）

// 归并排序非递归
void MergeSortNonRecursion(vector<int>& nums)
{
	int n = nums.size();
	vector<int> auxiliaryArr(nums.size());

	int gap = 1; // 需合并的子序列中元素的个数
	while (gap < n)
	{
		for (int k = 0; k < n; k += 2 * gap)
		{
			// 合并两个有序数组
			int cur1 = k, end1 = k + gap - 1;
			int	cur2 = k + gap, end2 = k + 2 * gap -1;
			int i = k;
			
			// 情况二：最后一组的第二个小区间不存在或是第一个小区间不够gap个，此时不需要对该小组进行合并
			if (cur2 >= n) break;
			// 情况一：最后一组的第二个小区间不够gap个，则第二个小区间的后界变为数组的后界
			if (end2 >= n) end2 = n - 1;
			//std::cout << "[" << cur1 << ", " << end1 << "] ";
			//std::cout << "[" << cur2 << ", " << end2 << "] ";

			while (cur1 <= end1 && cur2 <= end2)
			{
				if (nums[cur1] < nums[cur2])
				{
					auxiliaryArr[i++] = nums[cur1++];
				}
				else
				{
					auxiliaryArr[i++] = nums[cur2++];
				}
				
			}
			while (cur1 <= end1) auxiliaryArr[i++] = nums[cur1++];
			while (cur2 <= end2) auxiliaryArr[i++] = nums[cur2++];
		}
		// 还原数组 -- 把auxiliaryArr中排序好的数拷贝到nums数组
		for (int j = 0; j < n; j++)
		{
			nums[j] = auxiliaryArr[j];
		}
		//std::cout << endl;
		gap *= 2; // 下一趟需合并的子序列中元素的个数*2
	}
}

1.4 特性总结

  • 平均时间复杂度：O(n log n)
  • 空间复杂度：O(n)，因为需要额外的数组来存储合并结果。
  • 稳定性：稳定。
  • 适用场景：大量数据排序，外部排序。

--------------- END ---------------

「 作者 」 枫叶先生
「 更新 」 2024.9.8
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
          或有谬误或不准确之处，敬请读者批评指正。