【排序算法】归并排序

一、定义：

👉归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

二、递归思路：

✨✨首先根据定义，我们会发现和二叉树又又又联动了🤩🤩

归并排序是用分治思想，每一层递归上有三个步骤：
● 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
● 解决（Conquer）：用合并排序法对两个子序列递归的排序。
● 合并（Combine）：合并两个已排序的子序列得到排序结果。

🚗🚗发现了吗？？？我们好像是先从根开始的，这说明了啥？？？先动左子树，再动右子树，再动根，这个不就是🤔后续遍历么？

✨没错，确实就是模仿的后续遍历实现递归

🎟️排序：也是划分区间进行哎，将一个数组整个区间分成2个区间，然后将2个区间变成有序的，不知道有有没有写过2个有序数组的合并这个OJ题？？🧑‍🎓没写过也没问题，这里我们借助它的思路，2个有序数组的合并，创建第三方数组tmp，遍历2个数组，进行比较，谁小，谁的数据进入第三方数组tmp， 且下标加1，然后继续比较，直到有一方数组遍历结束，最后将剩下没有遍历完的数组中的数据放入tmp中👻👻

👻思路是这样的:

将数组分成2部分，其实相当于2个数组，这2个数组首先得是有序的，再进行有序数组的合并；

👉递归传递的是区间，区间相等即left==right时，不就只有一个数据，根本分不了区间了，此时可以看作就是有序的哦也就是👉画绿线的那一行

这也就是我们的结束条件：👉👉只有一个元素，递归结束，开始回推，回推的过程就开始合并2个有序数组的进行

✨✨ 首先我们对[0,1]这个区间二分，分成的区间都只有一个元素，可以看成有序，进行比较合并合并，回到上一层函数后，进入右边对[2,3]这个区间二分，同理，直接比较合并击即可🐸

🧑‍🎓🧑‍🎓🤔后续遍历是左、右子树然后是根节点，不就是回到10 6 7 1的这一层么，此时这里应该是如下所示的样子，然后对这个区间进行二分，分成的2个区间已然是有序的，进行2个数组合并即可，放到tmp中

放到tmp数组中之后，我们可以通过memcpy函数将tmp拷贝回原数组[0,3]这个区间；回推的过程依次类推

传递的是a+left，因为我们要放的位置是根据区间来放的，改变的是这个区间里面数据的顺序，拷贝回去也只能是a的这个区间，不然会将别的数据弄丢

有一个需要注意的点：就是传区间时，左和右区间的传参有一定的讲究，只能这么传

如果另一种传法，会导致陷入死循环，至于原因，目前本人不是很太能讲清楚，就先不写了

三、非递归：

将递归变成迭代的思想

🧑‍🎓之前用栈是因为我们来模拟递归，但是这里进行排序是在回推的时候进行的，在这里栈已经不行了 🧑‍🎓

那就试试直接用循环写呗，还记得之前插入排序的gap嘛？？？

🤔这里我们用gap记录元素个数，一开始gap=1 ，一组里面一个元素

区间不就是👉👉这样的么

然年第就是2个数归并

四四归，但是我们的最右边凑不出来四组，怎么办🤔🤔仔细看，不归并也行呢？？这个是有序数组，左边的归并后就是有序数组了，最后就是👉

左边和右边归并

✨✨核心在于gap组的控制：gap 2倍2倍的长，但是不能超过数组长度，区间二分嘛，2个区间

begin1，en1 begin2和end2 就是二分的2区间，将这2个区间进行归并

✨ 这里的数据是偶数，如果是奇数了？？？先别急🤗这个写法会发生越界访问，出不了结果的

👉看看我打印的区间：第一行正常，第二行正常，第三行，[12,15]越界了，第四行[8,15]一部分越界了

说明需要修改，卡看越界的特点，我们是【begin1，end1】和【begin2，end2】2个区间归并

第三行越界的区间正好是begin2 是不是可以去处理一下这个区间，当begin2>=n时候，打破循环，前面【8，11】在上一层下来的时候已经归并好了的

最后一层越界的是 end2，这里处理起来应该是要去修正，因为最后一行，要将[0,7][8,11]归并起来所以可以进行修正end2 = n-1

四、代码：

递归：

//子函数:实现递归
void _MergeSort(int* tmp, int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
    //防止栈溢出的写法，当然直接写(right+left)/2也行
	int mid = ((right-left)>>1)+left;
	_MergeSort(tmp, a, left, mid);
	_MergeSort(tmp, a, mid + 1,right);
	int begin1 = left;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = right;
	int i = 0;
	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 + left, tmp, (right - left + 1)*sizeof(int));

}
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(tmp, a, 0, n-1);
	free(tmp);
	tmp = NULL;
}

非递归：

//非递归归并
void MergeSortNonR(int* a, int n)
{
	//额外创造一个空间
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i+=2*gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap-1;
			int j = i;
			
			if (begin2>=n)
			{
				break;
			}	 
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			printf("[%d,%d][%d,%d]", begin1, end1, begin2, end2);
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			memcpy(a + i, tmp+i, sizeof(int)*(end2 - i + 1));

		}
		putchar('\n');
		gap *= 2;
	}


	free(tmp);
	tmp = NULL;
}

✨期待你的关注