数据结构——排序（归并排序）

目录

1.基本概念

2.分治策略的体现

3.时间复杂度和空间复杂度

4.稳定性

5.代码实现

1.基本概念

归并排序（Merge Sort）是一种基于分治策略的高效排序算法。它的核心思想是将一个数组分成两个或多个子数组，对每个子数组进行排序，然后将排序好的子数组合并成一个最终的有序数组。

2.分治策略的体现

1.分解（Divide）阶段：

1.对于一个给定的数组，归并排序会不断地将其分成更小的子数组。通常是将数组从中间位置分成两个子数组，这个过程是递归进行的。例如，对于数组[4, 7, 2, 6, 3, 8]，首先会被分为[4, 7, 2]和[6, 3, 8]两个子数组。然后这两个子数组又会继续被分割，[4, 7, 2]会被分为[4]、[7]和[2]，[6, 3, 8]会被分为[6]、[3]和[8]，直到每个子数组的长度为 1，此时认为这些长度为 1 的子数组是有序的。

2.解决（Conquer）阶段：

1.当子数组的长度为 1 时，开始进行合并操作。在合并过程中，会将两个已经有序的子数组合并成一个更大的有序数组。例如，将[4]和[7]合并为[4, 7]，将[2]和[4, 7]合并为[2, 4, 7]，以此类推。合并操作是归并排序的关键步骤，它通过比较两个子数组的元素，按照顺序将较小（或较大，取决于排序顺序）的元素依次放入一个新的临时数组中，直到其中一个子数组的元素全部放入临时数组，然后将另一个子数组剩余的元素也放入临时数组。

3.合并（Merge）阶段：

1.以合并两个有序子数组为例，假设有两个有序子数组A = [1, 3, 5]和B = [2, 4, 6]。首先比较A[0]和B[0]，因为1 < 2，所以将1放入临时数组，然后比较A[1]和B[0]，因为3 > 2，所以将2放入临时数组，接着比较A[1]和B[1]，以此类推。最后将临时数组中的元素复制回原数组，完成合并。

3.时间复杂度和空间复杂度

1.时间复杂度：

归并排序的时间复杂度在最好、最坏和平均情况下都是O(n*logn)。这是因为每次划分数组的时间复杂度为O(1)，而总共需要划分logn次（假设数组长度为n），每次合并操作的时间复杂度为O(n)，所以总的时间复杂度为O(n*logn)。例如，对于长度为 8 的数组，最多需要划分 3 次[log2(8)=3]，每次合并操作最多需要比较 8 次元素。

2.空间复杂度：

1.归并排序的空间复杂度为O(n)，因为在合并过程中需要使用一个额外的临时数组来存储合并后的元素，这个临时数组的长度与原数组长度相同。不过，有些优化的归并排序算法可以在一定程度上减少空间的使用，比如通过在原数组内部进行元素的交换和移动来实现合并，但一般情况下空间复杂度仍为O(n)。

4.稳定性

归并排序是一种稳定的排序算法。在合并两个有序子数组时，如果两个子数组中有相同的元素，按照顺序将它们放入临时数组，这样可以保证相同元素的相对顺序不变。例如，有两个子数组A = [2, 4]和B = [2, 3]，在合并时会先将A中的第一个2放入临时数组，然后将B中的2放入临时数组，从而保持了相同元素的相对顺序。

5.代码实现

一、函数功能概述

_MergeSort函数实现了归并排序的核心算法。它通过递归地将数组分成两个子数组，分别对两个子数组进行排序，然后将排序后的子数组合并成一个有序数组。

二、主要步骤解释

1. 递归划分数组：

   • if (left >= right)：如果当前子数组的范围只有一个元素或为空，直接返回，不再进行进一步的划分和排序。
   • int mid = (left + right) >> 1;：计算当前子数组的中间位置，将数组分为左右两个子数组。
   • _MergeSort(a, left, mid, tmp);和_MergeSort(a, mid + 1, right, tmp);：递归地对左右两个子数组进行排序。

2. 归并两个有序子数组：

   int begin1 = left, end1 = mid;和int begin2 = mid + 1, end2 = right;：分别定义两个子数组的起始和结束索引。
   • int index = left;：定义一个索引用于临时数组tmp的填充。
   • while (begin1 <= end1 && begin2 <= end2)：当两个子数组都还有元素未被处理时，循环进行比较和归并操作。
     • 如果a[begin1] < a[begin2]，将较小的元素a[begin1]放入临时数组tmp中，并将begin1和index分别递增。
     • 否则，将a[begin2]放入临时数组tmp中，并将begin2和index分别递增。
   • while (begin1 <= end1)和while (begin2 <= end2)：当其中一个子数组已经处理完，而另一个子数组还有剩余元素时，将剩余元素依次放入临时数组tmp中。

3. 将临时数组的值拷贝回原数组：

   for (int i = left; i <= right; ++i)：将临时数组tmp中的元素拷贝回原数组a，完成归并操作。

//归并思想上类似后序遍历
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)
		return;
	int mid = (left + right) >> 1;//右移==（left + right）/2
	// 假设 [left, mid] [mid+1, right]有序，那么我们就可以归并了
	_MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid + 1, right, tmp);

	// 归并  分成两个子区间
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = left;
	//两个区间，只要有一个begin>end就结束了
	//反之必须两个区间begin>end继续执行
	while (begin1 <= end1 && begin2 <= end2)
	{
		// 归并两个区间，依次对比取小的数放到新的临时数组
		if (a[begin1] < a[begin2])
		{
			tmp[index++] = a[begin1++];
		}
		else
		{
			tmp[index++] = a[begin2++];
		}
	}
	//看哪一个数组没有归并完，归并进去，只进行一个while
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}

	// 把临时数组的值拷贝回去原来数组
	for (int i = left; i <= right; ++i)
	{
		a[i] = tmp[i];
	}
}