算法04 七大排序之：归并排序

作者：nnngu
GitHub：https://github.com/nnngu
博客园：http://www.cnblogs.com/nnngu
简书：https://www.jianshu.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts

---

上一篇总结了直接插入排序和希尔排序，这一篇要总结的是归并排序，这也是七大排序的最后一种排序算法。

首先来看一下归并排序(Merge Sort) 的基本原理。它的原理是假设初始序列有n个元素，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，…… ，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法就称为归并排序。

1、归并排序的示意图

下面用示意图来说明归并排序的过程：

图一：

2、归并排序的代码

MergeSort.java

public class MergeSort {
    public static void main(String[] args) {
        int[] list = {50, 10, 90, 30, 70};
        System.out.println("************归并排序************");
        System.out.println("排序前：");
        display(list);
        System.out.println("");

        System.out.println("排序后：");
        mergeSort(list, new int[list.length], 0, list.length - 1);
        display(list);
    }

    /**
     * 归并排序算法
     *
     * @param list     待排序的列表
     * @param tempList 临时列表
     * @param head     列表开始位置
     * @param rear     列表结束位置
     */
    public static void mergeSort(int[] list, int[] tempList, int head, int rear) {
        if (head < rear) {
            // 取分割位置
            int middle = (head + rear) / 2;
            // 递归划分列表的左序列
            mergeSort(list, tempList, head, middle);
            // 递归划分列表的右序列
            mergeSort(list, tempList, middle + 1, rear);
            // 列表的合并操作
            merge(list, tempList, head, middle + 1, rear);
        }
    }

    /**
     * 合并操作(列表的两两合并)
     *
     * @param list
     * @param tempList
     * @param head
     * @param middle
     * @param rear
     */
    public static void merge(int[] list, int[] tempList, int head, int middle, int rear) {
        // 左指针尾
        int headEnd = middle - 1;
        // 右指针头
        int rearStart = middle;
        // 临时列表的下标
        int tempIndex = head;
        // 列表合并后的长度
        int tempLength = rear - head + 1;

        // 先循环两个区间段都没有结束的情况
        while ((headEnd >= head) && (rearStart <= rear)) {
            // 如果发现右序列大，则将此数放入临时列表
            if (list[head] < list[rearStart]) {
                tempList[tempIndex++] = list[head++];
            } else {
                tempList[tempIndex++] = list[rearStart++];
            }
        }

        // 判断左序列是否结束
        while (head <= headEnd) {
            tempList[tempIndex++] = list[head++];
        }

        // 判断右序列是否结束
        while (rearStart <= rear) {
            tempList[tempIndex++] = list[rearStart++];
        }

        // 交换数据
        for (int i = 0; i < tempLength; i++) {
            list[rear] = tempList[rear];
            rear--;
        }
    }

    /**
     * 遍历打印
     */
    public static void display(int[] list) {
        System.out.println("********展示开始********");
        if (list != null && list.length > 0) {
            for (int num :
                    list) {
                System.out.print(num + " ");
            }
            System.out.println("");
        }
        System.out.println("********展示结束********");
    }
}

运行结果：