算法导论 - 归并排序

老王

许多有用的算法在结构上是递归的，为了解决一个给定的问题，算法一次或多次递归地调用其自身以解决紧密相关的若干子问题。这些算法典型地遵循分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时都有三个步骤：

●  分解原问题为若干子问题，这些子问题是原问题的规模较小的实例；

●  解决这些子问题，递归地求解各子问题，如果子问题的规模足够小，则可以直接求解；

●  合并这些子问题的解以成为原问题的解。

归并排序算法完全遵循分治模式，其操作如下：

●  分解：分解待排序的n个元素的序列为各具n / 2个元素的两个子序列；

●  解决：使用归并排序算法递归地排序两个子序列；

●  合并：合并两个已排序的子序列以产生已排序的一个2 * 子序列。

当待排序的序列长度为1时，递归“开始回升”，在这种情况下不需要做任何工作，因为长度为1的每个序列都已排好序。

[C++] 纯文本查看 复制代码

#include <Windows.h>
#include <stdio.h>

// 归并排序
void Merge(int arrInt[], size_t nStart, size_t nMiddle, size_t nEnd)
{
    size_t nLeft   = nMiddle - nStart + 1;
    size_t nRight  = nEnd - nMiddle;
    int* pArrLeft  = malloc(sizeof(int) * nLeft);
    int* pArrRight = malloc(sizeof(int) * nRight);

    for (size_t i = 0; i < nLeft; i++)
        pArrLeft[i] = arrInt[nStart + i];
    for (size_t i = 0; i < nRight; i++)
        pArrRight[i] = arrInt[nMiddle + i + 1];

    for (size_t i = 0, j = 0, k = nStart; k <= nEnd; k++)
    {
        // 比较大小，并对左右数组进行越界检查
        if ((pArrLeft[i] <= pArrRight[j] && i < nLeft) || j >= nRight)
            arrInt[k] = pArrLeft[i++];
        else
            arrInt[k] = pArrRight[j++];
    }

    free(pArrLeft);
    free(pArrRight);
}

void MergeSort(int arrInt[], size_t nStart, size_t nEnd)
{
    if (nStart < nEnd)
    {
        size_t nMiddle = (nStart + nEnd) / 2;
        MergeSort(arrInt, nStart, nMiddle);
        MergeSort(arrInt, nMiddle + 1, nEnd);
        Merge(arrInt, nStart, nMiddle, nEnd);
    }
}

int main()
{
    int arrInt[] = { 5, 4, 3, 2, 1, 10, 9, 8, 7, 6, -1, -2, -3, -4, -5 };
    size_t nCount = sizeof(arrInt) / sizeof(arrInt[0]);

    MergeSort(arrInt, 0, nCount - 1);

    for (size_t i = 0; i < nCount; i++)
        printf("%d\n", arrInt[i]);

    return 0;
}