【数据结构】归并排序（用递归）

大家好，我是苏貝，本篇博客带大家了解归并排序，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

一. 基本思想

在讲归并排序之前，问问自己，如果有两个数组都是有序的（升序），如何将这两个有序数组合并成一个有序数组呢？如果没有思路，请先看看下面的博客吧
合并两个有序数组

了解了如何将两个有序数组合并成一个有序数组后（我们采用额外增加一个数组的方法），那如果这两个数组都不是有序数组呢？现在让我们来了解归并排序

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

在这里插入图片描述
将数组不断分成2部分，直到这两个部分都是一个元素，将这两个部分当成两个数组，因为都是只有一个元素，所以这两个数组都是有序的，再将两个有序数组合并成一个有序数组。如上图的10和6，经过合并成为一个有序数组6，10。再看10和6的右半边是1和7，将这两个部分当成两个数组，因为也是只有一个元素，所以这两个数组都是有序的，再将两个有序数组合并成一个有序数组1，7。然后将有序数组6，10和1，7再次合并成一个有序数组1，6，7，10……

归并排序动画演示：
在这里插入图片描述

二. 归并排序代码

在将两个有序数组合并成一个有序数组时，我们采用增加一个额外数组的方法。上述思路很明显可以用递归的方式来写代码，因为需要在函数内增加一个额外数组，所以不能递归这个函数（否则每次都会新增一个数组），所以我们来递归一个子函数。子函数中，当begin==end，表示只有一个元素，不用再递归。

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int midi = (begin + end) / 2;
	_MergeSort(a, begin, midi, tmp);
	_MergeSort(a, midi + 1, end, tmp);

	//归并
	int begin1 = begin, end1 = midi;
	int begin2 = midi + 1, 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 fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}