归并排序 | EXP Notes

基本概念

归并（Merge）排序是将两个或两个以上的有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

2-路归并排序（Merging Sort）

基本思想

初始待排序列有 n 个元素，可将其视为 n 个有序子序列，每个子序列长度为 1，然后两两合并，得 ⌈n/2⌉ 个长度为 2 或 1 的有序序列；然后继续两两合并，直到合并出一个长度为 n 的有序序列位置，此过程称为 2-路归并排序。

2-路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，即 Merge() 函数。

具体地，设两段有序序列 L[low…mid] 和 L[mid+1…high] 存放在同一顺序表中的相邻位置。
先将它们复制到辅助数组 T 中，然后每次从两段中选取较小的存入 L；
当 T 中某一段有剩余时，将其全部存入 A 中，合并完成。

代码实现

合并两个相邻子序列

// 使用全局辅助数组，长度为 n+1
int *T = (int *) malloc((n+1) * sizeof(int));
void Merge(int L[], int low, int mid, int high)
{
    int i, j, k; // k 为 A 中指针
    for (k=low; k<=high; ++k)
        T[k] = A[k];

    for (i=low, j=mid+1, k=i; i<=mid && j<=high; ++k)
    {
        if (T[i] <= T[j])
            A[k] = T[i++];
        elsek
            A[k] = T[j++];
    }
    // 复制剩余的部分，只有一个会执行
    while (i<=mid) A[k++] = T[i++];
    while (j<=high) A[k++] = T[j++];
}

基于分治法，使用递归调用合并函数，完成一趟归并排序。

分解：将 n 个元素分成各含 n/2 个元素的子序列，然后对两个子序列递归地进行排序；
合并：合并两个子序列完成排序。

void MSort(int L[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        MSort(L, low, mid);
        MSort(L, mid+1, high);
        Merge(L, low, mid, high);
    }
}

void MergeSort(int L[], int n)
{
    if (1 < n)  MSort(L, 1, n);
}

递归版归并实现简单，然而众所周知，递归效率不高，尤其当数据量较大时，需要很深的递归调用栈。

归并排序也可用迭代的方式实现

归纳分析

稳定排序（stable sort）

合并函数不会改变相同元素的相对顺序，因此2-路归并排序是稳定排序。

空间复杂度（out-of-place 非原地算法，O(n)）

合并元素需要 n 个辅助空间，（2-路）归并排序的空间复杂度为 O(n)。

上述代码中数组的 0 号空间没使用，因此代码中划分个 n+1 个大小的空间。

时间复杂度

分割子序列与初始状态无关；

一趟归并排序的操作，调用 ⌈n/2h⌉ 次合并函数将 L[1…n] 中前后相邻且长度为 h 的有序序列进行两两合并，得到前后相邻长度为 2h 的有序序列，每一趟排序（合并 Merge）时间为 O(n)，而整个归并需要进行 ⌈log₂n⌉ 趟。

无论何时，（2-路）归并排序时间复杂度为 O(nlog₂n)。

初态影响

由3分析可知，比较和移动操作的次数均与初始状态状态无关，因此初始状态堆递归排序影响不大。

过程特征

一趟排序无法确定一个元素的最终位置，会产生局部有序的子序列。

适用性

相比于同级别的快速排序和堆排序，归并排序是一种稳定排序，

不过相比快排，归并需要更多额外的空间，并且虽然时间复杂度是同一级别，但是归并的系数比快排大，所以速度比快排慢，

当然一般不单独使用归并排序，而是先用直接插入排序或者冒泡排序得到小的有序子序列后再使用归并。

算法证明（来自算法导论）

只要证明 merge() 函数的正确性即可。

merge函数的主要步骤在遍历比较回填，是由一个循环构成。

循环不变式：每次循环之前，L[low…k-1]已排序，且 T[i] 和 L[j] 是两段剩下元素中最小的两个。

初始：k=low，A[k…k-1] 为空，因此已排序，成立。

保持：在第 k 次迭代之前，A[low…k-1]已经排序，而因为 T[i] 和 T[j] 是剩下元素中最小的两个，因此只需要将 T[i] 和 T[j] 中最小的元素放到 A[k] 即可，在第 k+1 次迭代之前 A[low…k] 已排序，且 T[i] 和 T[j] 为剩下的最小的两个元素。

终止：k=high+1，且A[low…high]已排序，证毕。

算法优化

在序列长度为 k 时，用插入排序，因为插入排序适合对小数组排序。
这样一来，时间复杂度为 O(nk+nlg(n/k)) ，当 k=O(lgn)时，复杂度为O(nlgn)

void MSort(int L[], int len, int n)
{
    int i;
    // i+2len-1待合并的两段最大下标索引
    for (i=1; i+2*len-1<=n; i+=2*len)
        Merge(L, i, i+len-1, i+2*len-1);

    // i+2*len-1 > n，说明最后一段序列无法分成两个长度均为len的段

    // 要么一段为len，另一段小于len（i+len <= n < i+2*len-1）
    // 那么此时两段分别为L[i..i+len-1]和L[i+len..n]
    if (i+len <= n) Merge(L, i, i+len-1, n);

    // 要么只有一段，并且小于等于len（i+len > n）
    // 那么此时直接把这一段作为下一趟归并的段，将其全部追加到本趟归并序列之后
    // 此处不需要处理
}

void MergeSort(int L[], int n)
{
    int len;
    for (len=1; len<n; len*=2)
        MSort(L, len, n);
}

扩展

关于 k 路归并

一般而言，对于 N 个元素进行 k 路归并排序时，排序的趟数 m 满足 k_m = N，从而 m = log_kN，又考虑到 m 为整数，所以 m = ⌈log_kN⌉。

归并排序也是外部排序中的重要思想。

关于分治法

分治法就是将原问题分解为多个独立的子问题，且这些子问题的形式和原问题相似，只是规模上减少了，求解完子问题后合并结果构成原问题的解。

分治法通常有3步：

分解 Divide：将要解决的问题划分成若干规模较小的同类问题；
求解 Conquer：当子问题划分得足够小时，用简单的方法解决（递归）；
合并 Combine：按原问题的要求，将子问题的解逐层合并构成原问题的解。

假设 Divide 需要 f(n) 时间，Conquer 分解为 b 个子问题，且子问题大小为 a，Combine 需要 g(n) 时间，则递归式为：

T(n)=bT(n/a)+f(n)+g(n)

参数传递是进行递归调用的重要一步，传递不当就可能导致程序结果异常，甚至因为内存问题无法正常运行。

例如归并排序，

Divide 步骤为 m=(p+q)/2，时间复杂度为 O(1)，时间复杂度为 O(n)，Conquer 步骤为分解为 2 个子问题，子问题大小为 n/2，Combine 步骤为 Merge()函数，因此：

归并排序的递归式：T(n)=2T(n/2)+O(n)

求解递归式的三种方法有：

(1)替换法：主要用于验证递归式的复杂度。
(2)递归树：能够大致估算递归式的复杂度，估算完后可以用替换法验证。
(3)主定理：用于解一些常见的递归式。

上篇: 基数排序下篇: 选择排序

基本概念
2-路归并排序（Merging Sort）