07. 归并排序

1. 基本思想：

是将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2（n为奇数时，最后一个序列的长度为1）的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。这种方法被称作2-路归并排序。

采用了分治法的思想，分而治之，每个子问题的最优解最终组成大问题的最优解。

2. 归并操作：

把两个已排序的序列从第一个元素开始比较，小的放到新的序列表，把指针移动到下一个元素，如此比较直到一个序列指针指向空（一个序列已经全部加入新序列），把另一个序列的剩余元素加入到新序列尾部。

例如：序列{5，3，9，7，6，1，0}

初始状态：5，3，9，7，1，6，0

第一次归并：{3，5}{7，9}{1，6}{0} 比较3次

第二次归并：{3，5，7，9}{0，1，6} 比较3次

第三次归并：{0，1，3，5，6，7，9} 比较5次

总比较次数：N = 3+3+5 = 11次

3. 算法描述

1. 先申请一个可以放置两个序列大小的空间，作为这两个序列合并后的新序列。
2. 用两个指针分别指向这两个序列的第一个元素。
3. 比较两个指针指的元素的值，把值小的添加到新序列中，并把该指针向后移动一个。
4. 重复第3步，直到一个指针指向空（即一个序列已经全部添加），把另一个序列的剩余元素逐个添加到新序列末尾。

4. Java实现代码

public class MergeSort {

    // 自定义实现一次归并排序的函数
    void merge(Node[] r, Node[] s, int x1, int x2, int x3) {
        int i, j, k;
        i = x1; // 第一部分的开始位置
        j = x2 + 1; // 第二部分的开始位置
        k = x1;
        while (i <= x2 && j <= x3) {
            // 当i和j都在两个要合并的部分中时
            if (r[i].key <= r[j].key) {
                // 筛选两部分中较小的元素放到数组s中
                s[k] = r[i];
                i++;
                k++;
            } else {
                s[k] = r[j];
                j++;
                k++;
            }
        }

        // 将x1~x2范围内未比较的数顺次加到数组s中
        while (i <= x2) {
            s[k++] = r[i++];
        }

        // 将x2+1~x3范围内未比较的数顺次加到数组s中
        while (j <= x3) {
            s[k++] = r[j++];
        }

    }

    // 归并排序主函数
    void mergeSort(Node[] r, Node[] s, int m, int n) {
        int p = 0;
        Node[] t = new Node[20];
        if (m == n) {
            s[m] = r[m];
        } else {
            p = (m + n) / 2;

            // 递归调用mergeSort方法将r[m]~r[p]归并成有序的t[m]~t[p]
            mergeSort(r, t, m, p);

            // 递归调用mergeSort方法将r[p+1]~r[n]归并成有序的t[p+1]~t[n]
            mergeSort(r, t, p + 1, n);

            // 调用merge方法将前两部分归并到s[m]~s[n]
            merge(t, s, m, p, n);
        }
    }
}

5. 算法分析

时间效率：O(nlogn)

空间复杂度：T（n)

稳 定 性： 稳 定

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列