【排序算法】归并排序

封面画师：Nengoro(ネんごろぅ)     封面ID：77898217

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化     Data Structure Visualizations

执行流程：本文统一以升序为例子。

1. 归并排序

1.1 执行流程

归并排序（Merge Sort），在1945年由约翰·冯·诺依曼（John von Neumann）首次提出。

冯·诺依曼这个应该都很熟悉，什么？你不知道？看来你还没有体验过被计算机组成原理支配的恐惧。😭

执行流程

1、不断地将当前序列平均分割成 2 个子序列

• 直到不能再分割（序列中只剩一个元素）

2、不断地将 2 个子序列合并成一个有序序列

• 直到最终只剩下 1 个有序序列

归并排序示意图：

我们通常将分割阶段称之为： divide，将合并阶段称之为： merge。

1.2 divide

根据上面的归并排序示意图，我们发现：divide 的过程是将最初的数组切割成两个较小的数组，然后再将这两个较小的数组切割成更小的数组，然后一直切分，直到不能切分。

切割完后，进行排序合并，当然这是 merge 的过程了，我们先放一放。

我们很容易发现，divide的过程是一个递归的过程 ，大的切成较大的，较大的切成较小的，较小的切成最小的（然后对最小的进行merge，再对较小的进行merge，对较大的进行merge，最后对大的进行merge）。既然如此，为了使用递归我们可以在编写代码的时候重载一个排序方法。

由于切割的所有数据都是存在于同一个数组中的，因此我们需要知道切分序列的开始索引和结束索引。

那么我们归并排序的 “壳子” 就可以编写出来了：

public class MergeSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的数据进行归并排序
     *
     * @param begin 开始索引
     * @param end   排序数组的长度
     */
    private void sort(int begin, int end) { }
}

重载sort()方法后，设置了两个参数begin和end，具体含义已在代码中标出。

需要明白的一点是： end - begin就是某一序列中元素的数量。

在进行切割时，最多切割成只剩一个元素，因此这里有一个限制：end - begin < 2。

对于上图给出的归并排序示意图，我们可以发现：对一个大序列进行归并排序可以看成对两个较大的序列进行归并排序，对较大的序列进行归并排序时又可以看成对两个小的序列进行归并排序。

观察切割过程，我们基本是将排序的序列进行对半切分的（奇数情况时有一边会多一个），此时我们前面在设计begin和end的优点就可以体现出来了。

对于大序列分成两个小序列进行归并排序时，令mid = (end - begin) >> 1，则：

• 对左边的小序列来说，数据范围是[begin, mid)
• 对右边的小序列来说，数据范围是[mid, end)

这样设计有一个好处，数据范围都是半开半闭，便于操作。

那么divide过程的代码就可以编写出来了：

public class MergeSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的数据进行归并排序
     *
     * @param begin 开始索引
     * @param end   排序数组的长度
     */
    private void sort(int begin, int end) {
        // end - begin 是元素的数量
        if (end - begin < 2) return;
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        // 切割后还要进行排序合并
        ......
    }
}

进行切割后，需要对这些小序列进行排序合并，这些序列都在同一个数组中，因此我们需要指定进行合并的每个小序列的开始索引、结束索引和切割位置。那么可得 merger 方法的“壳子”为：

/**
 * 将 [begin,end) 和 [mid,end) 范围的序列合并成一个有序数列
 *
 * @param begin 开始
 * @param mid   中间
 * @param end   结束
 */
private void merge(int begin, int mid, int end) {
 	// 省略实现代码   
}

在归并排序示意图中，我们可以发现，进行merge操作时的两个序列都是挨在一起的，数据范围都是左闭右开的，这也证明了我们的参数设置是没有问题的。

将merge()方法添加到重载的sort()方法中：

private void sort(int begin, int end) {
    // end - begin 是元素的数量
    if (end - begin < 2) return;
    int mid = (begin + end) >> 1;
    sort(begin, mid);
    sort(mid, end);
    merge(begin, mid, end);
}

那 merge 过程的具体实现应该是怎样的呢？👇

1.3 merge

假设现有两个序列，我们需要对其合并，这两个序列中的元素都是有序的，合并的时候从头开始进行比较合并即可。因此，我们可以使用两个指针分别指向两个序列的第一个位置的索引，然后用这两个索引位置的元素进行比较。具体步骤可以看下图：

merge 步骤示意图：

在上图中，前两个序列（数组）是独立的，而最后放元素的数组相对于前两个序列也是独立的。简单来说，上图所示的三个数组都是独立的，是三块独立的内存。

如果全都是独立的就好了，做法就很简单。

但是现实是残酷的，真正的归并排序需要 merge 的 2 组序列存在于统一数组中，并且是挨在一起的 ，而且最后合并而成的数组也是在同一块内存中的。

PS： end 指的是数组长度，设置区间时就半开半闭。

因此，就不能使用我们前面的那种方法。

那我们应该怎么做？

为了更好的完成 merge 操作，最好将其中 1 组序列备份出来，比如： [begin, mid)

因为需要升序排序，所以可以选择备份左边的序列。

在上图中，很容易得到索引关系为：

• li == 0， le == mid - begin
• ri == mid， re == end

---

l 指 left； r 指 right。

i 指 index； e 指 end。

实例分析

merge一般情况：

merge左边数组先结束：

merge右边数组先结束：

在merge时，如果左边先结束（li == le时），我们什么都不用干，右边已经排序好了；如果右边先结束，我们需要将左边的元素一个一个赋值到右边，不断进行li++, ai++的操作。

merge代码实现

/**
 * 将 [begin,end) 和 [mid,end) 范围的序列合并成一个有序数列
 *
 * @param begin 开始
 * @param mid   中间
 * @param end   结束
 */
private void merge(int begin, int mid, int end) {
    int li = 0, le = mid - begin;
    int ri = mid, re = end;
    int ai = begin;

    // 备份左边数组
    for (int i = li; i < le; i++) {
        // 大数组范围是 [begin, end)，而非从索引0开始
        leftArray[i] = array[begin + i];
    }
    while (li < le) { // 左边还没结束
        // 注意顺序与稳定性的关系
        if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
            array[ai++] = array[ri++];
        } else {
            array[ai++] = leftArray[li++];
        }
    }
}

---

为了保持稳定性，我们在进行比较时，需要：

• cmp(leftArray[li], array[ri]) <= 0
• 或者cmp(array[ri], leftArray[li]) < 0

可以通过下面的数组验证稳定性：

1.4 完整代码

package com.yang.sort;

/**
 * @author 默烦
 * @date 2020/8/14
 */
public class MergeSort<E extends Comparable<E>> extends Sort<E> {
    private E[] leftArray;

    @Override
    protected void sort() {
        leftArray = (E[]) new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的数据进行归并排序
     *
     * @param begin 开始索引
     * @param end   排序数组的长度
     */
    private void sort(int begin, int end) {
        // end - begin 是元素的数量
        if (end - begin < 2) return;
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, mid, end);
    }

    /**
     * 将 [begin,end) 和 [mid,end) 范围的序列合并成一个有序数列
     *
     * @param begin 开始
     * @param mid   中间
     * @param end   结束
     */
    private void merge(int begin, int mid, int end) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;

        // 备份左边数组
        for (int i = li; i < le; i++) {
            // 大数组范围是 [begin, end)，而非从索引0开始
            leftArray[i] = array[begin + i];
        }
        while (li < le) { // 左边还没结束
            // 注意顺序与稳定性的关系
            if (ri < re && cmp(array[ri], leftArray[li]) < 0) {
                array[ai++] = array[ri++];
            } else {
                array[ai++] = leftArray[li++];
            }
        }
    }
}

代码测试

生成 2w 个随机数，范围是[1, 20000] ，方法耗时如下：

经过测试后：我们发现归并排序相当优秀，它不仅是一个稳定的排序算法，耗时甚至比堆排序还少。

耗时比堆排序还少，难道归并排序的时间复杂度比堆排序还少？或者类似？

1.5 复杂度分析

在我们的归并排序代码中，使用了递归操作，正因如此，使用原来的方法来分析时间复杂度变得困难。

我们可以使用递推公式来计算归并排序的时间复杂度。

我们假设归并排序花费的时间为： T(n) = 2 * T(n / 2) + O(n)

T 表示时间 Time，n 表示数据规模，T(n)则表示数据规模为 n 的数据进行归并排序所用的时间。

PS：进行merger操作时，我们需要遍历两边的数组，因此可以认定其时间复杂度为：O(n)

而我们最终是需要求得归并排序的时间复杂度，即： T(n) = O(x)，我们需要求得其中的 x 。

手写求解过程如下：

由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是O(nlogn)，属于稳定排序 。

从代码也不难看出： 归并排序的空间复杂度是O(n / 2 + logn) = O(n) 。

---

常见的递推式与复杂度：

2. “顶级”排序

注意：纯属段子，切勿当真！ 😹

史上“最强”排序——休眠排序！

排序类：

public class SortThread extends Thread {
    private int value;

    public SortThread(int value) {
        this.value = value;
    }

    public void run() {
        try {
            Thread.sleep(value);
            System.out.println(value);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

测试类：

public static void main(String[] args) {
    int[] array = {10, 100, 50, 30, 60};
    for (int i = 0; i < array.length; i++) {
        new SortThread(array[i]).start();
    }
}

我们甚至可以发现这个排序的时间复杂度竟为O(n)！ 😆