标签：归并 -- 算法 nbsp arr1 排序 arr2

归并排序

归并排序的思想

归并排序运用了典型的分治策略，是一种稳定的排序算法，其时间复杂度为 \(O(nlogn)\) ，空间复杂度为 \(O(n)\)。
分治的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。分治策略一般适用于解决一个问题的多个实例，而且这些实例之间有许多共通的特征。很多递归算法都包含着分治的思想。为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干个子问题^[1]。而对于归并操作，就是指将两个已经排序好的子序列合并成一个有序序列的过程^[2]。
分治模式在每一层递归上都有三个步骤^[1:1]：
1. 分解(Divide)原问题为若干子问题，这些子问题的形式与原问题相同，只是规模更小；
2. 解决(Conquer)步骤递归地求解出子问题，如果子问题的规模足够小，则停止递归，直接求解；
3. 合并(Combine)步骤将子问题的结果合并成原问题的解。

归并排序完全遵守分治模式，其具体的步骤如下^[1:2]：
1. 分解：将待排序的 \(n\) 个元素分成各包含 \(n/2\) 个元素的子序列；
2. 解决：使用归并排序递归地排序两个子序列；
3. 合并：合并两个已排序的子序列以得到排序结果。

归并排序的过程如下图所示：

flowchart TD arr1_01[9] arr1_02[6] arr1_03[5] arr1_04[8] arr1_05[7] arr1_06[4] arr1_07[3] arr1_08[0] arr1_09[1] arr1_10[2] arr2_01["6#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;9"] arr2_02["5#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;8"] arr2_03["4#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;7"] arr2_04["0#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;3"] arr2_05["1#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;2"] arr3_01["5#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;6#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;8#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;9"] arr3_02["0#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;3#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;4#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;7"] arr3_03["1#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;2"] arr4_01["0#nbsp;#nbsp;#nbsp;#nbsp;3#nbsp;#nbsp;#nbsp;#nbsp;4#nbsp;#nbsp;#nbsp;#nbsp;5#nbsp;#nbsp;#nbsp;#nbsp;6#nbsp;#nbsp;#nbsp;#nbsp;7#nbsp;#nbsp;#nbsp;#nbsp;8#nbsp;#nbsp;#nbsp;#nbsp;9"] arr4_02["1#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;2"] arr5_01["0#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;1#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;2#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;3#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;4#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;5#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;6#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;7#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;8#nbsp;#nbsp;#nbsp;#nbsp;#nbsp;9"] arr1_01 --> arr2_01 arr1_02 --> arr2_01 --> arr3_01 arr1_03 --> arr2_02 arr1_04 --> arr2_02 --> arr3_01 --> arr4_01 arr1_05 --> arr2_03 arr1_06 --> arr2_03 --> arr3_02 arr1_07 --> arr2_04 arr1_08 --> arr2_04 --> arr3_02 --> arr4_01 --> arr5_01 arr1_09 --> arr2_05 arr1_10 --> arr2_05 --> arr3_03 --> arr4_02 --> arr5_01

推荐这篇文章的示意图，非常直观：排序——归并排序（Merge sort）。

归并排序的实现

2.1 《算法导论》中的实现

^[1:3]

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1 + 1] = ∞
    R[n2 + 1] = ∞
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else A[k] = R[j]
            j = j + 1

MERGE-SORT(A, p, r)
    if p < r
        q = ⌊(p + r) / 2⌋
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q + 1, r)
        MERGE(A, p, q, r)

2.2 《数据结构（第2版）》中的实现

^[2:1]

/* L=右边起始位置，R=右边起始位置，RightEnded=右边终点位置 */
void Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd)
{
    /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp;
    int i;

    LeftEnd = R - 1; /* 左边终点位置 */
    Tmp = L;         /* 有序序列的起始位置 */
    NumElements = RightEnd - L + 1;

    while (L <= LeftEnd && R <= RightEnd)
    {
        if (A[L] <= A[R])
            TmpA[Tmp++] = A[L++];   /* 将左边元素复制到TmpA */
        else
            TmpA[Tmp++] = A[R++];   /* 将右边元素复制到TmpA */
    }

    while (L <= LeftEnd)
        TmpA[Tmp++] = A[L++];    /* 直接复制左边剩下的 */
    while (R <= RightEnd)
        TmpA[Tmp++] = A[R++];   /* 直接复制右边剩下的 */

    for (i = 0; i < NumElements; i++, RightEnd--)
        A[RightEnd] = TmpA[RightEnd];   /* 将有序的TmpA[]复制回A[] */
}

void MSort(ElementType A[], ElementType TmpA[], int L, int RightEnd)
{
    /* 核心递归排序函数 */
    int Center;

    if (L < RightEnd)
    {
        Center = (L + RightEnd) / 2;
        MSort(A, TmpA, L, Center);      /* 递归解决左边 */
        MSort(A, TmpA, Center + 1, RightEnd);   /* 递归解决右边 */
        Merge(A, TmpA, L, Center + 1, RightEnd);   /* 合并两段有序序列 */
    }
}

void MergeSort(ElementType A[], int N)
{
    /* 归并排序 */
    ElementType *TmpA;
    TmpA = (ElementType *)malloc(N * sizeof(ElementType));

    if (TmpA != NULL)
    {
        MSort(A, TmpA, 0, N - 1);
        free(TmpA);
    }
    else
        printf("空间不足");
}

2.3 数据结构（C语言版）》中的实现

^[3]

void Merge(RcdType SR[], RcdType TR[], int i, int m, int n)
{
    /* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
    int j, k, l;
    for (j = m + 1, k = i; i <= m && j <= n; k++)
    {
        if (SR[i].key <= SR[j].key)
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    if (i <= m)
    {
        for (l = 0; l <= m - i; l++)
            TR[k + l] = SR[i + l];  /* 将剩余的SR[i..m]复制到TR */
    }
    if (j <= n)
    {
        for (l = 0; l <= n - j; l++)
            TR[k + l] = SR[j + l];  /* 将剩余的SR[j..n]复制到TR */
    }
}

void MSort(RcdType SR[], RcdType TR1[], int s, int t)
{
    /* 将SR[s..t]归并排序为TR1[s..t] */
    int m;
    RcdType TR2[MAXSIZE + 1];
    if (s == t)
        TR1[s] = SR[s];
    else
    {
        m = (s + t) / 2;    /* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
        MSort(SR, TR2, s, m);   /* 递归地将SR[s..m]归并为有序的TR2[s..m] */
        MSort(SR, TR2, m + 1, t);   /* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
        Merge(TR2, TR1, s, m, t);   /* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
    }
}

void MergeSort(SqList *L)
{
    /* 对顺序表L作归并排序 */
    MSort(L.r, L.r, 1, L.length);
}

2.4 个人常用的模版

上面提到的几个实现都是为了讲解方便，按顺序写出来的，但是在算法比赛中的时候，我更倾向简洁一点的代码。模板来自《AcWing 787. 归并排序的证明与边界分析》^[4]。我自己做了注释，方便理解。

void mergeSort(int a[], int l, int r)
{
    //递归的终止情况
    //当l >= r时，说明数组只有一个元素，不需要再分解
    if(l >= r) return;

    //第一步：分成子问题
    int mid = l + r >> 1;

    //第二步：递归处理子问题
    //这里于快速排序不同，快排是先递归，再合并
    //由于每次都现递归，所以等于将数组划分为一个元素一组
    mergeSort(a, l, mid );
    mergeSort(a, mid + 1, r);

    //第三步：合并子问题
    //这里的合并子问题是指将两个有序的数组合并成一个有序的数组
    //由于每次划分都是从中间划分，所以左右两边的数组都是有序的
    //这里的关键就是处理边界问题
    //左边数组的边界为[l, mid], 右边数组的边界为[mid + 1, r]
    //所以合并的时候，需要从左边数组的第一个元素开始，和右边数组的第一个元素开始比较
    int k = 0,          //临时数组的下标
        i = l,          //左边数组的下标
        j = mid + 1,    //右边数组的下标
        tmp[r - l + 1]; //临时数组
    //这里的边界条件是i <= mid && j <= r，而不是i < mid && j < r 
    //因为当i == mid时，左边数组只有一个元素，而且这个元素是最后一个元素
    //我们需要让合并的两个数组里的其中一个数组的元素全部放入临时数组
    while(i <= mid && j <= r)  
        if(a[i] <= a[j])
            tmp[k++] = a[i++];  //左边数组的元素小于右边数组的元素，将左边数组的元素放入临时数组
        else 
            tmp[k++] = a[j++];  //右边数组的元素小于左边数组的元素，将右边数组的元素放入临时数组
    //将剩余的元素放入临时数组
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(k = 0, i = l; i <= r; k++, i++) 
        a[i] = tmp[k];  //将临时数组的元素放回原数组
}

归并排序代码上的分析

若要深刻理解归并排序，必须首先理解归并排序的思想，以及它的排序过程。然后思考如何将这个过程转化为代码。

我们再来看一下前文提到的归并排序的过程：
1. 分解：将待排序的 \(n\) 个元素分成各包含 \(n/2\) 个元素的子序列；
2. 解决：使用归并排序递归地排序两个子序列；
3. 合并：合并两个已排序的子序列以得到排序结果。

//TODO

参考与注释：

《算法导论》 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 机械工业出版社 ↩︎ ↩︎ ↩︎ ↩︎
《数据结构（第2版）》陈越高等教育出版社 ↩︎ ↩︎
《数据结构（C语言版）》严蔚敏, 吴伟民清华大学出版社 ↩︎
《AcWing 787. 归并排序的证明与边界分析》 ↩︎

标签：归并,--,算法,nbsp,arr1,排序,arr2
From： https://www.cnblogs.com/BryceAi/p/17726811.html

【算法】归并排序算法