【算法与数据结构】归并排序的代码实现（详细图解）以及master公式的讲解

灰太狼 2023-10-16 17:19 25阅读 0赞

![1b3ce4bb3de94b90953975eba91e2ffe.png][]

**目录**

1、归并排序

1.1、算法描述

1.2、图解说明

2、代码实现

3、master公式

3.1、公式以及结论

3.2、适用于某些特殊的递归

3.3、计算归并排序的时间复杂度

![32f7d3c8fd15401d8056dddf220a1d1e.gif][]

## 1、归并排序 ##

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

### 1.1、算法描述 ###

>  *  把长度为n的输入序列分成两个长度为n/2的子序列；
>  *  对这两个子序列分别采用归并排序；
>  *  将两个排序好的子序列合并成一个最终的排序序列。
> 
> 而将两个的有序数列合并成一个有序数列，我们称之为"归并"，这就是归并排序名字的由来。

### 1.2、图解说明 ###

> 一句话简单说：对L到R范围排序，可以先求出L到R的中点M。先让左侧数据排好序，然后再让右侧数据排好序，此时再将两个有序子序列整合成一个新的有序序列。

![7eb7d56aed5f4349a2a1d6d6f35f5e06.png][]

例如：

> **对一个数组\[8,3,6,4,2,1,5,7\]进行归并排序。**

**第一步：**把长度为n的输入序列分成两个长度为n/2的子序列，新的子序列再分别分成两个长度为自身一半也就是n/4的子序列，以此类推。当分到单个子序列只剩下一个数字时，一个数字就是天然了有序，即此时左侧和右侧都排好序了。

![973e96c92e2249dbba99787d75ac3123.png][]

**第二步：**将两个排序好的子序列合并成一个新的排序序列。首先在每个子序列中都有一个指针指向子序列的第一个元素，两个指针的元素两两比较，较小的元素先放入新的子序列中，然后指针挪动继续比较，直至全部放入新的子序列当中，即完成一次子序列合并。慢慢合并最终使所有元素都成有序，即完成归并排序。

![e4286c5c7f664ccdb3addde4da9426a9.png][]

> 这个思路过程是非常精髓的，理解了这个思路之后，就可以试着用代码实现了。

## 2、代码实现 ##

> 要使用归并，首先需要知道数组arr以及数组最左L下标和最右R下标，因此需要求出并带入MergeSort当中。

int main()
    {
    	int arr[10] = { 8,3,6,4,2,1,5,7 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	MergeSort(arr, 0, sz - 1);
    	int i = 0;
    	for ( i = 0; i < sz; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    }

> 接下来看看MergeSort的实现。
> 
> 1.  首先是判断L是否等于R，如果L和R相等时就相当于是单个子序列中只存在了一个元素，而此时该子序列就为有序，因此不用进行操作直接返回即可，即if(L == R) return；
> 2.  如果L不等于R时则认为该子序列中仍然可拆分，便求出mid中间值，并分别进行两次递归让两块递归范围有序，递归范围是L到mid、mid+1到R。
> 3.  最后当递归结束时则代表L到mid、mid+1到R序列已有序，整体还无序，此时需要使用ExternalSort外部排序将这两个子序列整合成一个新的有序序列。

void MergeSort(int* arr, int L, int R)
    {
    	if (L == R)  //子序列只有一个数，默认为有序
    	{
    		return;
    	}
    	int mid = L + (R - L) / 2;
    	MergeSort(arr, L, mid);
    	MergeSort(arr, mid + 1, R);
    	ExternalSort(arr, L, mid, R);
    }

> ExternalSort的作用就是让arr中的L到M、M+1到R合并成一个新的有序序列，并将判断后的结果序列先存入到help指针指向的区域，等待完成所有合并，再将help整个区域的数据拷贝到arr对应的位置。
> 
> 而存入help的**规则**是：
> 
> 1、如果p1和p2都没有越界进行while循环：
> 
> p1和p2比较，如果p1大于p2，则将p2所指向的元素放入help中，然后将p2右移指向下一个，继续下一轮比较。
> 
> p1和p2比较，如果p1小于等于p2，则将p1所指向的元素放入help中，然后将p1右移指向下一个，继续下一轮比较。
> 
> 2、如果有一方越界了，则退出循环，并判断p1和p2中哪个还有剩余的元素未排入help中，如果有则直接排入到help中。

![09f377caf19f4722aac9bde3d04ce025.png][]

void ExternalSort(int* arr, int L, int M, int R)
    {
    	int* help = (int*)malloc(sizeof(int) * (R - L + 1)); //辅助空间，用于存放排序后的数据，空间大小为R-L+1。
    	if (help == NULL)
    	{
    		perror("ExternalSort->malloc");
    		return;
    	}
    	int helpSz = R - L + 1;
    	int i = 0;
    	int p1 = L;
    	int p2 = M + 1;
    	while (p1 <= M && p2 <= R)
    	{
            //判断p1是否小于等于p2，如果是则将p1指向的值放入help数组中然后两指针前进一位，反之p2亦然
    		help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    	}
    	while (p1 <= M)   //如果p1还没越界，则将剩余的元素全部拷贝到help之后
    	{
    		help[i++] = arr[p1++];
    	}
    	while (p2 <= R)   //如果p2还没越界，则将剩余的元素全部拷贝到help之后
    	{
    		help[i++] = arr[p2++];
    	}
    	for ( i = 0; i < helpSz; i++)
    	{
    		arr[L + i] = help[i];    //将合并完成的数据拷贝回原数组arr的对应位置
    	}
    	free(help);
    	help = NULL;
    }

> 到这里，归并排序的代码实现部分就结束了，总的来说因为使用的是递归，代码量是不多的，但是最难的是理解归并排序的思路， 需要好好体会归并排序的操作步骤和思路。

## 3、master公式 ##

> 那么完成了归并排序之后，我想知道这个排序的时间复杂度是多少的话，我该怎么算？有人说当然是直接百度搜索一下就知道了。我想说的是这样确实是没问题，但是秉持着**“授人以鱼不如授人以渔”**的理念，我想带大家深入了解并让大家学会自己去**计算递归的时间复杂度**。
> 
> 而用来计算的公式就是使用**master公式：**在计算涉及递归的算法的时候，计算复杂度就会变得有些麻烦。master公式就是用来进行剖析递归行为和递归行为时间复杂度的估算的。

### 3.1、公式以及结论 ###

*  master公式：**T(N) = a\*T(N/b) + O(N^d)**
 *  **![T(N) = a \* T(\\frac\{N\}\{b\})+O(N^\{d\})][T_N_ _ a _ T_frac_N_b_O_N_d]**
 *  公式解释：**N**表示母问题的规模。**N/b**表示子问题的规模，子问题规模必须相同，即都为N/b。**a**表示递归的次数也就是子问题在母问题中被调用了多少次。**O(N^d)**表示除了递归调用操作以外其余操作的复杂度。
 *  结论（证明过于复杂，只需要记住结论即可）：

1.  当公式中的a、b、d符合d<logb a时，时间复杂度为O(N^(logb a))
2.  当公式中的a、b、d符合d=logb a时，时间复杂度为O((N^d)\*logN)
3.  当公式中的a、b、d符合d>logb a时，时间复杂度为O(N^d)

*  **注意：master公式适用于一些特殊的递归，就是子问题规模必须等分，不管你是分成几部分，就算是划分的区域有重叠，只要区域大小一致，就都可以使用。**

**【举例说明】**

> 下面是一个使用递归实现在一个数组中找最大值的代码，这里是使用**二分法**来快速查找最大值，子问题的划分大小是一致的，因此可以使用**master公式**计算时间复杂度。
> 
> 1.  首先可以看到process中自身调用了两次process，母问题中有**两个子问题调用**，**即a=2**。
> 2.  然后由于是二分法，因此每个子问题的规模是母问题规模的一半，**即N/2**。
> 3.  接着再看其他操作，其他操作都只执行一次，即时间复杂度为**O(1)**。
> 4.  最后：该递归的master公式就是**T(N) = 2 \* T(N/2) + O(1)。**
> 
> **即a = 2, b = 2, d = 0，代入结论公式得d<logb a，时间复杂度为O(N^(logb a)) = O(N)**

int process(int* arr, int L, int R)
    {
    	if (L == R)
    		return arr[L];
    	int mid = L + (R - L) / 2;
    	int leftMAX = process(arr, L, mid);    //左半边
    	int rightMAX = process(arr, mid + 1, R);   //右半边
    	return leftMAX > rightMAX ? leftMAX : rightMAX;
    }
    
    int main()
    {
    	int arr[] = { 8,3,6,4,2,1,5,7 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	int max = process(arr, 0, sz - 1);
    	printf("%d\n", max);
    	return 0;
    }

### 3.2、适用于某些特殊的递归 ###

> 上面说到过：master公式适用于一些特殊的递归，就是子问题规模必须等分，不管你是分成几部分，就算是划分的区域有重叠，只要区域大小一致，就都可以使用。
> 
> **但是仍然会有些人会误解意思，下面使用图解的方式给大家解释一下。**

**【图解说明】**

> 首先，**等分区域**是最容易理解的，就是将N等分成若干份，二分就是N/2，三分就是N/3。

![29706ef481d348ff967139222d799af9.png][]

> 子问题的规模是左侧三分之二和右侧三分之二，这样的符合master公式吗？
> 
> 答案是**符合**的，因为这里只关注的是**区域大小是否一致**，而不关心区域是否重叠。

![b35da24b2d134ff09ac0cb360c4f43bd.png][]

> 子问题规模不一样，不符合master公式。

![eb17435761864b43a7cafd48584e2860.png][]

### 3.3、计算归并排序的时间复杂度 ###

> 学完了master公式，那么我们就来计算一下**归并排序**的时间复杂度吧。

> 假设整个过程的数据量是N的规模，两个子问题都是T(N/2)，因此是2\*T(N/2)。
> 
> 那么现在来观察除了子问题外的其他语句：if语句是**O(1)**的时间复杂度，而ExternalSort函数的两个指针都只往右前进不会回退的遍历所有数据一遍，又因为数据量是N的规模，所以ExternalSort函数的时间复杂度是**O(N)**。
> 
> **即：T(N) = 2 \* T(N/2) + O(N) 其中a = 2，b = 2，d = 1**
> 
> **将a、b、d代入结论公式得d=logb a，时间复杂度为O((N^d)\*logN) = O(N\*logN)。**

![fa7a99697df648379f732974bd7d1845.gif][]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[1b3ce4bb3de94b90953975eba91e2ffe.png]: https://img-blog.csdnimg.cn/1b3ce4bb3de94b90953975eba91e2ffe.png
[32f7d3c8fd15401d8056dddf220a1d1e.gif]: https://img-blog.csdnimg.cn/32f7d3c8fd15401d8056dddf220a1d1e.gif
[7eb7d56aed5f4349a2a1d6d6f35f5e06.png]: https://img-blog.csdnimg.cn/7eb7d56aed5f4349a2a1d6d6f35f5e06.png
[973e96c92e2249dbba99787d75ac3123.png]: https://img-blog.csdnimg.cn/973e96c92e2249dbba99787d75ac3123.png
[e4286c5c7f664ccdb3addde4da9426a9.png]: https://img-blog.csdnimg.cn/e4286c5c7f664ccdb3addde4da9426a9.png
[09f377caf19f4722aac9bde3d04ce025.png]: https://img-blog.csdnimg.cn/09f377caf19f4722aac9bde3d04ce025.png
[T_N_ _ a _ T_frac_N_b_O_N_d]: https://latex.csdn.net/eq?T%28N%29%20%3D%20a%20*%20T%28%5Cfrac%7BN%7D%7Bb%7D%29&plus;O%28N%5E%7Bd%7D%29
[29706ef481d348ff967139222d799af9.png]: https://img-blog.csdnimg.cn/29706ef481d348ff967139222d799af9.png
[b35da24b2d134ff09ac0cb360c4f43bd.png]: https://img-blog.csdnimg.cn/b35da24b2d134ff09ac0cb360c4f43bd.png
[eb17435761864b43a7cafd48584e2860.png]: https://img-blog.csdnimg.cn/eb17435761864b43a7cafd48584e2860.png
[fa7a99697df648379f732974bd7d1845.gif]: https://img-blog.csdnimg.cn/fa7a99697df648379f732974bd7d1845.gif