【原】归并排序的实现

归并排序

归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。
归并：将两个或两个以上的有序序列合并成一个有序序列的过程。

具体流程可用如下图片表示：

我们采用的归并方法通常为二路归并排序，即将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。

归并排序有三大关键问题，分别是：

（1）如何将两个有序序列合成一个有序序列？
（2）怎样算完成一趟归并？
（3）如何控制二路归并的结束？

我们将这三个问题拆解为三个方法来分析。

关键问题（1）：如何将两个有序序列合成一个有序序列？

由于在归并过程中，可能会破坏原来的有序序列，所以，我们将归并的结果存入另外一个保存结果的数组中。我们在两个有序序列的头部设上指针i和j，不断选择i, j所指向的较小元素；并通过结果数组的k指针，将该元素放入结果数组的末尾。

代码如下：

void Merge(int *r, int *r1, int s, int m, int t) {
    int i = s;
    int j = m + 1;
    int k = s;
    while (i <= m && j <= t) {
        if (r[i] < r[j]) {
            r1[k++] = r[i++];
        } else {
            r1[k++] = r[j++];
        }
    }
        // 收尾处理
    if (i <= m) {
        while (i <= m) {
            r1[k++] = r[i++];
        }
    }

    if (j <= t) {
        while (j <= t) {
            r1[k++] = r[j++];
        }
    }
}

参数列表中，r为需要排序的数组，r1为结果数组，s表示第一个有序序列的头索引，m表示第一个有序序列的尾索引，t表示第二个有序序列的尾索引。

关键问题（2）：怎样算完成一趟归并？

首先，我们规定：在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度h表示；数组总长度为n（下标为0到n - 1）

因为每一次归并我们都对相邻的两个有序序列进行操作，所以为了解决这个问题，我们可以判断第二个有序序列尾索引的位置。假设i为第一个有序序列的头索引，分析可知，第二个有序序列尾索引为(i + 2h - 1)。

a.如果(i + 2h - 1) < n

则说明相邻两个有序表的长度均为h，执行一次归并（调用Merge），完成后i加2h，准备进行下一次归并。

如果不满足a情况，则说明数组剩余的长度不足以取出两个长度为h的有序序列进行排序，则又有两种可能的情况：

b.如果(i + h) < n

(i + h)指向的是第二个有序序列的头索引，这说明第二个有序序列存在，但是长度不足h，此时第二个序列的尾索引位置并不能直接为(i + 2h - 1)，而是(n - 1)。

c.如果(i + h) >= n，即不满足b情况

说明不存在第二个有序序列，仅剩下最后一个，此时只要将该有序序列的元素送到结果数组的相应位置即可。

代码如下：

void MergePass(int *r, int *r1, int n, int h) {
    int i = 0;
    while (i + 2 * h - 1 < n) {    // 情况a
        Merge(r, r1, i, i + h - 1, i + 2 * h - 1);
        i += 2 * h;
    }
    if (i + h < n) {    // 情况b
        Merge(r, r1, i, i + h - 1, n - 1);
    } else {    // 情况c
        for (int j = i; j < n; j++) {
            r1[j] = r[j];
        }
    }
}

参数列表中，r为需要排序的数组，r1为结果数组，n表示数组总长度，h表示有序序列的长度。

关键问题（3）：如何控制二路归并的结束？

这个问题的解决方法就是归并排序的思想了，即开始时，有序序列的长度h=1；每做一趟归并后（调用MergePass）h = 2h；结束时，有序序列的长度h=n，用有序序列的长度来控制排序的结束。

代码如下：

void MergeSort(int n, int *r) {
    int h = 1;
    int r1[maxn] = {0};
    while (h < n) {
        MergePass(r, r1, n, h);
        h = 2 * h;
        // 将结果数组r1的结果赋值到待排序数组r中
        for (int i = 0; i < n; i++) {
            r[i] = r1[i];
        }
        // 将结果数组r1重新置0
        memset(r1, 0, n * sizeof(int));
    }
}

以上就可以解决归并排序问题啦！

写一个主函数，并在MergeSort()中加入显示数组，我们可以看到效果如下

附上全部代码：

#include <iostream>
#include <memory.h>

using namespace std;

int maxn = 1000;

void printArray(int *a, int n) {
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            cout << a[i];
        } else {
            cout << " " << a[i];
        }
    }
    cout << endl;
}

void Merge(int *r, int *r1, int s, int m, int t) {
    int i = s;
    int j = m + 1;
    int k = s;
    while (i <= m && j <= t) {
        if (r[i] < r[j]) {
            r1[k++] = r[i++];
        } else {
            r1[k++] = r[j++];
        }
    }
    if (i <= m) {
        while (i <= m) {
            r1[k++] = r[i++];
        }
    }

    if (j <= t) {
        while (j <= t) {
            r1[k++] = r[j++];
        }
    }
}

void MergePass(int *r, int *r1, int n, int h) {
    int i = 0;
    while (i + 2 * h - 1 < n) {
        Merge(r, r1, i, i + h - 1, i + 2 * h - 1);
        i += 2 * h;
    }
    if (i + h < n) {
        Merge(r, r1, i, i + h - 1, n - 1);
    } else {
        for (int j = i; j < n; j++) {
            r1[j] = r[j];
        }
    }
}

void MergeSort(int n, int *r) {
    int h = 1;
    int count = 0;  // 用于记录趟数
    int r1[maxn] = {0};
    while (h < n) {
        count++;
        MergePass(r, r1, n, h);
        h = 2 * h;

        for (int i = 0; i < n; i++) {
            r[i] = r1[i];
        }
        // 显示数组
        cout << "第" << count << "趟归并，h为" << h << ":" << endl;
        printArray(r, n);

        memset(r1, 0, n * sizeof(int));
    }
}

int main() {
    int n, mer[maxn];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> mer[i];
    }

    MergeSort(n, mer);
    return 0;
}