【经典算法】归并排序

浏览数：33 / 时间：2015年06月08日

　　归并排序是以O(NlogN)最坏情形运行时间运行，而所使用的比较次数几乎是最优的。它是递归算法的一个很好的实例。

　　归并排序的也遵循分治的思想。直观上其操作如下：

　　分解：分解待排序的n个元素的序列成各具n/2个元素的子序列。

　　解决：使用归并排序递归地排序两个子序列。

　　合并：合并两个已排序的子序列以产生已排序的答案。

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

　　归并排序算法的关键操作是“合并步骤”中两个已排序序列的合并。我们通过调用一个辅助过程Merge(A,p,q,r)来完成合并，其中A是一个数组，p,q,r是数组下标，满足p≤q＜r。该过程假设子数组A[p,...,q]和A[q+1,...,r]都已经排好序。它合并这两个子数组形成单一的已排好序的子数组并代替当前的子数组A[p,...,r]。

　　过程Merge的思想如下：取两个已排序的输入数组A[p,...,q]和A[q+1,...,r]以及一个临时输出数组B，令i=p，表示的是A[p,...,q]的索引；j=q+1，表示的是A[q+1,...,r]的索引；k=0，表示的是临时输出数组B的的索引。A[i]和B[j]的较小者被复制到B的下一个位置，相关计数器向前推进一步。当两个输入表有一个用完的时候，则将领一个表中的剩余部分拷贝到C中。

　　代码如下：

void Merge(int *, int, int, int);

void MergeSort(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        MergeSort(A, p, q);
        MergeSort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

void Merge(int A[], int p, int q, int r) {
    int *B = new int[r - p + 1];
    int i = p, j = q + 1, k = 0;
    while (i <= q && j <= r) {
        if (A[i] <= A[j]) {
            B[k++] = A[i++];
        } else {
            B[k++] = A[j++];
        }
    }

    while (i <= q) {
        B[k++] = A[i++];
    }

    while (j <= r) {
        B[k++] = A[j++];
    }

    for (k = 0; k < r - p + 1; k++)
        A[p + k] = B[k];

    delete []B;
}