【排序】归并排序算法

特别说明：

对于算法，重在理解其思想、解决问题的方法，思路。因此，以下内容全都假定待排序序列的存储结构为：顺序存储结构。

归并排序算法介绍

归并排序算法主要是将两个有序的序列合并成一个更大些的有序序列。因此归并排序算法要有个归并操作(这也是其核心操作)。归并操作，总是将两个相邻的有序序列进行合并，直至整个待排序序列最终有序。该算法与快速排序算法类似，也是采用分治思想，将待排序序列每次折半拆分(折半拆分的终止条件为当序列的元素个数为1个时停止)，分别进行归并处理。在每一趟的归并操作过程中，都并非原地执行，而是需要(与待排序序列一样大小的额外)辅助空间进行的。因此，归并排序的空间复杂度为 $O(n)$ 。另外，在具体实现上，归并排序可以使用递归实现，也可以使用非递归实现。

归并排序算法(递归法)思想

假设待排序序列为 $R_{1..n}$ ，则归并排序算法描述为：

01.刚开始时，每个元素当成一个有序序列，执行 02 步骤；

02.将序列相邻两个元素进行归并操作，完成后整个 $R_{1..n}$ 被划分成 $\left \lceil \frac{n}{2} \right \rceil$ 个有序序列，且每个序列元素个数为 2 个或 1 个；

03.重复 02 步骤，进行归并操作，直至整个待排序序列有序为止。(注意：每经过一次 02 步骤的归并操作后，有序序列的元素个数都增加一倍)；

归并操作

归并操作是整个排序算法的关键操作，需要申请额外辅助空间 $H_{1..n}$ 。假设两个领的有序序列分别为 $R_{l..m}$ 与 $R_{m+1..h}$ ，则可以设置3个标记，标记 $i$ 指向 $R_{l..m}$ 中当前待(归并)处理的元素位置，标记 $j$ 指向 $R_{m+1..h}$ 中当前待(归并)处理的元素位置，标记 $k$ 指当向 $H_{1..n}$ 的当前可填入元素位置。只要 $i$ < $m$ 且 $j$ < $h$ ，就将 $R_{i}$ 与 $R_{j}$ 中较小者拷贝到 $H_{k}$ ，然后 $k$ = $k$ + 1 ，同时 $i$ ， $j$ 中较小者也加 1。最后，将 $R_{l..m}$ 与 $R_{m+1..h}$ 中仍剩余的元素一并拷贝到辅助空间 $H_{1..n}$ 中 $k$ 之后空间上，到此一趟归并操作完成。

设额外申请的辅助空间为 $H_{1..n}$ ，则归并操作描述如下：

01.设置标记 $i$ = $l$ ； $j$ = $m$ + 1； $k$ = $l$ ；

02.如果 $i$ < $m$ 且 $j$ < $h$ ，则执行 03 步骤，否则执行 04 步骤；

03.如果 $R_{i}$ < $R_{j}$ ，则执行 $H_{k}$ = $R_{i}$ ； $i$ = $i$ + 1； $k$ = $k$ + 1，跳转并执行 02 步骤；

如果 $R_{i}$ $\geqslant$ $R_{j}$ ，则执行 $H_{k}$ = $R_{j}$ ； $j$ = $j$ + 1； $k$ = $k$ + 1，跳转并执行 02 步骤；

04.如果 $i$ < $m$ ，则将 $R_{i..m}$ 按顺序拷贝到 $H_{k}$ 及之后的空间中；

05.如果 $j$ < $h$ ，则将 $R_{j..h}$ 按顺序拷贝到 $H_{k}$ 及之后的空间中；

归并排序算法编码实现参考

说明：此处实现的是递归版本。

 1 // 
 2 // summary     : 归并排序的合并操作.(即:将两个相邻的有序子序列合并为一个大的有序序列)
 3 // in param    : seqlist 待排序列表.同时也是排完序列表.
 4 // in param    : helplist 辅助空间序列.
 5 // in param    : nLow 待合并的相邻有序子序列(序列1)的低端.
 6 // in param    : nMid 待合并的相邻有序子序列(序列1)的高端,同时 nMid + 1 也是相邻有序子序列(序列2)的低端.
 7 // in param    : nHigh 待合并的相邻有序子序列(序列2)的高端.
 8 // out param   : --
 9 // return      : --
10 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
11 void merge_part(int seqlist[/*nLen*/], int helplist[/*nLen*/], const int nLow, const int nMid, const int nHigh) {
12     auto helpIndex = nLow;
13     auto lowIndex  = nLow;
14     auto highIndex = nMid + 1;
15     while (lowIndex <= nMid && highIndex <= nHigh) {
16         helplist[helpIndex++] = seqlist[lowIndex] < seqlist[highIndex] ? seqlist[lowIndex++] : seqlist[highIndex++];
17     }
18     for (; lowIndex <= nMid; ++lowIndex, ++helpIndex) {
19         helplist[helpIndex] = seqlist[lowIndex];
20     }
21     for (; highIndex <= nHigh; ++highIndex, ++helpIndex) {
22         helplist[helpIndex] = seqlist[highIndex];
23     }
24     for (helpIndex = nLow; helpIndex <= nHigh; ++helpIndex) {
25         seqlist[helpIndex] = helplist[helpIndex];
26     }
27 }
28 
29 // 
30 // summary     : 归并排序算法实现.
31 // in param    : seqlist 待排序列表.同时也是排完序列表.
32 // in param    : helplist 辅助空间列表.
33 // in param    : nLow 待排序序列的低端.
34 // in param    : nHigh 待排序序列的高端.
35 // out param   : --
36 // return      : --
37 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
38 //               02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的.
39 void m_sort_recursive(int seqlist[/*nLen*/], int helplist[/*nLen*/], const int nLow, const int nHigh) {
40     if (nLow == nHigh) {
41         helplist[nLow] = seqlist[nLow];
42     } else if (nLow < nHigh) {
43         const auto nMid = (nLow + nHigh) >> 1;
44         m_sort_recursive(seqlist, helplist, nLow, nMid);
45         m_sort_recursive(seqlist, helplist, nMid + 1, nHigh);
46         merge_part(helplist, seqlist, nLow, nMid, nHigh);
47     }
48 }
49 
50 // 
51 // summary     : 归并排序算法实现.(对外提供,其实功能与m_sort()是完全一样的,只是该接口方便使用)
52 // in param    : seqlist 待排序列表.同时也是排完序列表.
53 // in param    : nLen 列表长度
54 // out param   : --
55 // return      : --
56 // !!!note       : 01.以下实现均假设一切输入数据都合法.即:内部不对参数全法性进行校验,默认它们全都合法有效.
57 //               02.排序开始前 seqlist 是无序的,排序结束后 seqlist 是有序的.
58 void merge_sort_recursive(int seqlist[/*nLen*/], const int nLen) {
59     int* helplist = new int[nLen];
60     m_sort_recursive(seqlist, helplist, 0, nLen - 1);
61     for (auto nIdx = 0; nIdx < nLen; ++nIdx) {
62         seqlist[nIdx] = helplist[nIdx];
63     }
64     delete [] helplist;
65 }

归并排序算法C++编码实现参考(递归版本)

归并排序算法分析

前面已经讲过，归并排序算法的空间复杂度为 $O(n)$ ，其时间复杂度为多少？由前面的算法思想可见(注意：前面的算法思想其实是二路归并排序思想)，该算法最终是形成一棵二叉树，且树的深度为 ${log_{2}}^{n}$ ，该树是自底向上建成的 (即：从树的叶子节点一直往树根方向生成整棵树)。当根节点生成时，则整个待排序序列就已经排好序，除根节点外的任何一个节点的数据元素量都为共父节点的一半。每个树节点执行归并操作的耗时都依赖于该节点的元素个数，每个节点操作的时间计为 $c$ $n$ ，因此，整个归并排序算法的时间为 $T(n) = 2T(\frac{n}{2}) + cn$ ，该递归式的解为 $kn{log_{2}}^{n}$ (注：有不明白该解是如何来的，请查阅【排序】快速排序算法文章介绍)。因此归并排序算法的时间复杂度为 $O(nlg^{n})$ 。另外，归并排序算法是稳定排序算法排序算法。