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

1、归并排序

1.1、算法描述

1.2、图解说明

2、代码实现

3、master公式

3.1、公式以及结论

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

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

1、归并排序

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

若将两个有序表合并成一个有序表，称为二路归并。

1.1、算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

而将两个的有序数列合并成一个有序数列，我们称之为"归并"，这就是归并排序名字的由来。

1.2、图解说明

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

例如：

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

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

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

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

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的实现。

首先是判断L是否等于R，如果L和R相等时就相当于是单个子序列中只存在了一个元素，而此时该子序列就为有序，因此不用进行操作直接返回即可，即if(L == R) return；
如果L不等于R时则认为该子序列中仍然可拆分，便求出mid中间值，并分别进行两次递归让两块递归范围有序，递归范围是L到mid、mid+1到R。
最后当递归结束时则代表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中。

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})$
公式解释：N表示母问题的规模。N/b表示子问题的规模，子问题规模必须相同，即都为N/b。a表示递归的次数也就是子问题在母问题中被调用了多少次。O(N^d)表示除了递归调用操作以外其余操作的复杂度。
结论（证明过于复杂，只需要记住结论即可）：

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

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

【举例说明】

下面是一个使用递归实现在一个数组中找最大值的代码，这里是使用二分法来快速查找最大值，子问题的划分大小是一致的，因此可以使用master公式计算时间复杂度。

首先可以看到process中自身调用了两次process，母问题中有两个子问题调用，即a=2。
然后由于是二分法，因此每个子问题的规模是母问题规模的一半，即N/2。
接着再看其他操作，其他操作都只执行一次，即时间复杂度为O(1)。
最后：该递归的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。

子问题的规模是左侧三分之二和右侧三分之二，这样的符合master公式吗？

答案是符合的，因为这里只关注的是区域大小是否一致，而不关心区域是否重叠。

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

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

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

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);
}

假设整个过程的数据量是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)。