【数据结构】归并排序 —— 递归及非递归解决归并排序

一、归并排序

1、归并排序的思想

假设我们要排一个升序的数组
先看下面的动图

假设有两组升序数据
我们设置 ptr1 和 ptr2 来代表数组下标
将两数据进行比较，将小的填入一个新的数组
当两个数组中的数都进入新的数组
接下来我们只需要将该数组复制到原数组中
就完成了排序

如果我们要排一个升序数组
就要将它分成两个小的升序数组

若想得到两个小的升序数组
就要将每一个小的升序数组分成两个更小的升序数组

。。。。。。

————————————————————————————
于是我们想到了用递归的方式
一层层递归
直到只剩下一个不用数据，然后返回进行排序

2、归并排序代码实现（递归）

void _MergeSort(int* a, int* tmp, int left, int right)
{
	//返回停止条件
	if (left == right)
	{
		return;
	}

	//取中间值
	int mid = (left + right) / 2;
	
	//递归
	//[left, mid][mid + 1, right]
	//递归左边
	_MergeSort(a, tmp, left, mid);
	//递归右边
	_MergeSort(a, tmp, mid + 1, right);

	//进行单次归并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	//记录起始位置
	int begin = left, end = right;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[begin++] = a[begin1++];
		}
		else 
		{
			tmp[begin++] = a[begin2++];
		}
	}
	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 MergeSort(int* a, int left, int right)
{
	//开辟一个复制数组
	int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
	if (tmp == NULL)
	{
		perror("malloc fail:");
		exit(1);
	}

	//进行归并排序
	_MergeSort(a, tmp, left, right);

	//数组销毁
	free(tmp);
	tmp = NULL;
}

<1> 归并排序的递归区间

递归区间1
[left, mid][mid + 1, right]
递归区间2
[left, mid - 1][mid, right]

看这两个区间有所不同
上面代码我采用的是区间1
而没有采用区间2
因为区间2会出现死循环，导致栈溢出
看下面的图：

区间1：

区间2：

同样的 mid 但是当递归至只剩下两个时，区间2就会陷入死循环

<2> 归并排序的稳定性

while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[begin++] = a[begin1++];
		}
		else 
		{
			tmp[begin++] = a[begin2++];
		}
	}

在比较 begin1 和 begin2 时我们用的是 " <= "
这样前面的数就会在前面

在图上我们发现我们在面对相同的数时，我们会先将 ptr1 中的数填入数组，那么相同数的相对位置没有发生改变，我们说归并排序是稳定的

<3> 拷贝

//进行拷贝
memcpy(a + left, tmp + left, sizeof(int) * (right - left + 1));

我们是边排序边拷贝的
如果等到最后拷贝会有出问题的风险
memcpy函数

3、归并排序代码实现（非递归）

如果是用非递归的方式
我们可以用循环
设置gap变量，gap 每次循环结束 gap *= 2
完成整个数组的归并

代码实现：

//归并排序(非递归)
void MergeSortNonR(int* a, int left, int right)
{
	//开辟复制数组
	int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
	if (tmp == NULL)
	{
		perror("malloc fail:");
		exit(1);
	}

	int gap = 1;
	//进行单次排序
	while (gap < right + 1)
	{
		for (int i = 0; i < right + 1; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			int begin = i;
			printf("[%d, %d][%d, %d]", begin1, end1, begin2, end2);
			
			//当begin2超过数组区间
			if (begin2 > right)
			{
				break;
			}
			//当只有end2超过区间
			if (end2 > right)
			{
				end2 = right;
			}

			//单次归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[begin++] = a[begin1++];
				}
				else
				{
					tmp[begin++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[begin++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[begin++] = a[begin2++];
			}
			//将数组进行复制
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}
		printf("\n\n");
		gap *= 2;
	}

	//销毁复制数组
	free(tmp);
	tmp = NULL;
}

<1> 循环区间溢出问题

当begin2超过数组区间
if (begin2 > right)
{
	break;
}
当只有end2超过区间
if (end2 > right)
{
	end2 = right;
}

在循环过程中，除了 begin1 不会超出数组区间
其他三个都有可能超出区间
我们将所有区间都打印出来

我们发现超出区间总共分为三种情况

当 begin2 和 end1 超出区间时：
说明后面的整个区间都超出了数组的范围
那就不用归并

当 end2 超出区间时：
说明后面的一部分数没有超出区间
可以将 end2 改为区间的最大值，继续进行归并

二、总结

归并排序的时间复杂度为 O(N * logN)
是比较快的排序
但是归并排序有它的缺陷
它的空间复杂度为 O(N)
排序需要开辟空间
当排序数量过大时有风险