[数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

矫情吗；* 2023-10-13 18:43 83阅读 0赞

**目录**

1、归并的思想

2、归并排序的思想

2.1 基本思想

2.2 图解分析

3、归并排序递归版本代码实现

3.1 代码解析

3.2 注意事项

3.2.1错误划分：\[begin, mid-1\]，\[mid, end\]

3.2.2 正确划分：\[begin, mid\], \[mid+1, end\]

4、归并排序的测试

5、时间复杂度、空间复杂度分析

5.1 时间复杂度

5.2 空间复杂度

--------------------

## 1、归并的思想 ##

这是我们第二次了解归并的思想了，第一次在我们之前的链表oj题里面，合并两个有序链表，我们当时解题的思想就是归并的思想。

> 我们这次来系统的学习一下归并的思想（**本篇以升序为例展开**）：
> 
> 归并两个数组（链表）时，我们使用两个指针指向不同的数组首元素，控制并遍历两个数组，比较两个指针指向的值，小的我们放入开辟的临时数组里面，然后让指向小值的指针往后走一步，继续比较。不断去比，总有一个数组先被遍历完，由于是有序数组，另外那个没有被遍历完的数组直接连接到临时数组的后面就完成了排序。

我们画图来理解这个思想：

![b1d26c8a5c56aa83d2ac3bd2e57f63f8.png][]

## 2、归并排序的思想 ##

### 2.1 基本思想 ###

> 归并排序是建立在归并操作上的一种有效的排序算法。
> 
> 1.归并排序的思想是，将一个数组二分为左右两个数组，然后对左右两个数组继续进行二分，直到分为的子区间为一个数据的时候，这一个数据一定是有序的，便不再二分。
> 
> 2.接下来就对左右两个子区间进行排序合并，不断排序合并，最终就实现了整个数组的排序。

### 2.2 图解分析 ###

![e354fff204f95dfdfbc0e0600e3f73a7.png][]

我们归并的时候**不是直接在原数组上就交换的，直接在原数组上操作会产生覆盖，导致****错误****。因此我们是malloc一个与原数组大小相同的空间tmp，将每次合并后的值拷贝到tmp中，****合并一次拷贝一次，最中tmp数组为有序，再将tmp使用memcpy拷贝回原数组****，再free(tmp) （防止内存泄漏），整个排序就完成了。**

## 3、归并排序递归版本代码实现 ##

// 归并排序递归实现
    // 时间复杂度：O(N*logN)
    // 空间复杂度：O(N + logN)
    void _MergeSort(int* a, int begin, int end, int* tmp)
    {
    	if (begin >= end)
    		return;
    
    	int mid = (begin + end) / 2;
    	//[begin, mid] [mid+1, end]
    	_MergeSort(a, begin, mid, tmp);
    	_MergeSort(a, mid+1, end, tmp);
    
    	int begin1 = begin, end1 = mid;
    	int begin2 = mid + 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 (NULL == tmp)
    	{
    		perror("malloc fail:");
    		return;
    	}
    	_MergeSort(a, 0, n-1, tmp);
    	free(tmp);
    }

### 3.1 代码解析 ###

![836455ad2a2e0d6aec2412eb12427add.png][]

**我们在这一段使用了递归，递归的思想就是二分，将数组分为左右两个区间，然后再对左右两个区间继续进行二分，当 begin >= end 时，就是最小的区间，然后我们就进行排序+合并。**

![3eabd05d2373605aff2646d1ea69a01d.png][]

这一段就是排序+合并，我们对两个子区间进行排序+合并，思路就是我们归并的思想。这里要**注意，我们tmp的下标是begin，因为我们需要将每一层合并的值先放进tmp中，然后再拷贝到原数组里，如果是0，拷贝回去的时候就会出现错误。**

### 3.2 注意事项 ###

在划分左右区间的时候**一定是 \[begin, mid\]，\[mid+1, end\]，**

**不能是 \[begin, mid-1\]，\[mid, end\]！！！**

**这里很容易出错，看着逻辑上没问题，但是在排序的时候就会出问题。**

#### 3.2.1错误划分：\[begin, mid-1\]，\[mid, end\] ####

![96d123e7df0492798ac0788e4ce5a6c6.png][]

#### 3.2.2 正确划分：\[begin, mid\], \[mid+1, end\] ####

![ed0215c9ea2ecd0d78685bba09cde04b.png][]

**总结：****造成第一种划分死循环的原因是，当我们 mid = begin+end/2 时，计算器是向下取整的，所以一旦向下取整的时候，我们的区间就要包含mid这个值，这样就会补上向下取整造成的舍去。**

## 4、归并排序的测试 ##

void Print(int* a, int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    }
    void _MergeSort(int* a, int begin, int end, int* tmp)
    {
    	if (begin >= end)
    		return;
    
    	int mid = (begin + end) / 2;
    	// [begin, mid] [mid+1, end]
    	_MergeSort(a, begin, mid, tmp);
    	_MergeSort(a, mid + 1, end, tmp);
    
    	int begin1 = begin, end1 = mid;
    	int begin2 = mid + 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 (NULL == tmp)
    	{
    		perror("malloc fail:");
    		return;
    	}
    	_MergeSort(a, 0, n - 1, tmp);
    
    	free(tmp);
    }
    void test()
    {
    	int a[] = { 6,3,2,1,5,7,9 };
    	Print(&a, sizeof(a) / sizeof(int));
    	MergeSort(&a, sizeof(a) / sizeof(int) - 1);
    	Print(&a, sizeof(a) / sizeof(int));
    }
    int main()
    {
    	test();
    
    	return 0;
    }

*测试结果：*

![e15cf61fa9f1cf3dffbfc3408129a7af.png][]

## 5、时间复杂度、空间复杂度分析 ##

## 5.1 时间复杂度 ##

归并排序区间不断二分，时间复杂度为O(logN)；然后再合并，时间复杂度为O(N)。

**整体的时间复杂度为o(N\*logN)。**

### 5.2 空间复杂度 ###

因为我们开辟了一个临时空间用于排序，因此**空间复杂度O(N)。**

[b1d26c8a5c56aa83d2ac3bd2e57f63f8.png]: https://img-blog.csdnimg.cn/img_convert/b1d26c8a5c56aa83d2ac3bd2e57f63f8.png
[e354fff204f95dfdfbc0e0600e3f73a7.png]: https://img-blog.csdnimg.cn/img_convert/e354fff204f95dfdfbc0e0600e3f73a7.png
[836455ad2a2e0d6aec2412eb12427add.png]: https://img-blog.csdnimg.cn/img_convert/836455ad2a2e0d6aec2412eb12427add.png
[3eabd05d2373605aff2646d1ea69a01d.png]: https://img-blog.csdnimg.cn/img_convert/3eabd05d2373605aff2646d1ea69a01d.png
[96d123e7df0492798ac0788e4ce5a6c6.png]: https://img-blog.csdnimg.cn/img_convert/96d123e7df0492798ac0788e4ce5a6c6.png
[ed0215c9ea2ecd0d78685bba09cde04b.png]: https://img-blog.csdnimg.cn/img_convert/ed0215c9ea2ecd0d78685bba09cde04b.png
[e15cf61fa9f1cf3dffbfc3408129a7af.png]: https://img-blog.csdnimg.cn/img_convert/e15cf61fa9f1cf3dffbfc3408129a7af.png