常见排序算法之归并排序

目录

一、什么是归并排序

二、递归实现

2.1 思路

2.2 C语言源码

三、非递归实现

3.1 思路

3.2 C语言源码

一、什么是归并排序

归并排序是一种基于分治思想的排序算法。它的基本思想是将原始的待排序序列不断地分割成更小的子序列，直到每个子序列中只有一个元素，然后逐步将这些子序列合并为一个有序的序列。

具体来说，归并排序的操作流程如下：

1. 分割阶段：将待排序序列不断地二分为更小的子序列，直到每个子序列只包含一个元素。
2. 合并阶段：将相邻的子序列两两合并，合并过程中按照大小顺序排列元素，直到所有的子序列合并为一个有序序列。

归并排序由于是自上而下的递归排序，每次合并操作都需要额外的空间来存储临时的序列，因此归并排序的空间复杂度较高。但由于合并操作是稳定的，因此归并排序是一种稳定的排序算法。

归并排序的时间复杂度为 O(nlogn)，其中 n 为待排序序列的长度，因此归并排序在时间上具有较高的效率。由于其稳定性和高效性，归并排序通常被用于需要稳定性的排序场景，或者对于大数据量的排序。

可以看出，归并排序类似于快速排序的思想，都是基于分治法的二叉树思路实现。但是二者存在区别：

• 快速排序是一种类似前序的思路-先排序大区间再排序小区间
• 归并排序是一种类似后序的思路-先排子区间再排大区间最后合并

这样的区别会体现在代码实现中递归代码的位置上。

二、递归实现

2.1 思路

核心思路：将每个小区间数组在新数组上排序，然后复制回原数组上。重复递归，由小区间到大区间，直至排序完成

• 考虑单次

1. 比较逻辑：两个区间分别初始化两个指针指向起始位置，逐个元素遍历比较，按照大小顺序放入新数组中。
2. 收尾逻辑：区间内或许存在顺序已经排好的序列，比较逻辑结束后将他们放入新数组中
3. 最后将新数组拷贝到原数组中，一个区间排序完成

• 考虑递归

1. 每次计算区间的中点进行二分法
2. 传入[起始位置，中点] 以及 [中点的下一个位置，结束位置] 进行重复递归
3. 递归结束的条件是，子区间仅有一个元素（意味着不需要排列）

注意事项：

实际写代码的过程中，每次开辟空间的做法大大降低了程序执行的效率。更好的处理方法是：开辟于要排序数组等大的空间，每次小区间复制只需传入区间的起始位置，区间的大小就可以避免空间的重复开辟。

2.2 C语言源码

//递归版本
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin == end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//递归
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//归并
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;

	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
		
	}
	//收尾
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = 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");
		exit(1);
	}
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	tmp = NULL;
}

三、非递归实现

3.1 思路

与快速排序的非递归实现思路类似，本质上仍然是要控制每次传入的区间。但是前文有讲二者的细微差别，所以实现方式不尽相同。本文采用二路循环方式的方式实现。

采用自底向上的思路讲解

比较的主题逻辑依然是采用上述递归思路的逻辑，所以仍然需要两个指针指向两个组，gap变量表示每组处理的数据。

• 考虑一次处理：
  gap=1，两路，处理的是两个数据。排序后将中间数组复制到原数组的指定位置
• 考虑一层处理：因为二路处理一次只能有限个数据，需要再来一次循环处理掉该层的所有数据。结束条件很明显要小于数组的大小，每次循环起始位置都是原位置+2*gap
  
• 考虑循环处理：一层结束后，下一层gap要变成原来的2倍。很明显循环结束条件是gap小于数组大小。

注意事项：

上述图解的元素个数恰好是偶数，若出现奇数个的情况，在求区间时一定会发生数组越界的情况。需要找到特殊情况然后进行修正

1. 由于begin1指针由数组大小循环来控制，所以不可能造成越界。
2. 考虑end1越界：那么后续的两个指针同样越界，此时区间内只有一个元素无需排序，跳出循环即可
3. 考虑begin2越界：此时区间内有两个元素，在上一层排序中二者已经为有序，所以跳出循环即可。
4. 考虑end2越界：此时第二个组中仅有一个元素，依然需要比较排序。所以需要将end2的下标进行修正。

3.2 C语言源码

//非递归版本
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc");
		exit(1);
	}
	
	int gap = 1;	// 每组归并的数据个数

	while (gap < n)
	{
		for (int j = 0; j = n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			//开始排序
			int i = j;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[i++] = a[begin1++];
				}
				else
				{
					tmp[i++] = a[begin2++];
				}
			}
			//收尾
			while (begin1 <= end1)
			{
				tmp[i++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[i++] = a[begin2++];
			}
			//每组结束复制
			memcpy(a + j, tmp + j, sizeof(int) * (end2 - j + 1));
		}
		//循环
		gap *= 2;
	}
}