「归并排序」之归与并，分与治？

vlambda
2022-03-09

「归并排序」之归与并，分与治？

考察归并排序的题目可以形态各异，但总会有万变不离其宗，希望看完今日之章，你能掌握归并排序及其思想大成。

归并排序

归并排序和之前的冒泡排序、插入排序和选择排序不同，其蕴含了一种分治的思想，关于分治和递归的思想之前有分享一篇文章，感兴趣的可以作为参考，不过在今天的图文中，同样会看到这两个思想。

话不都说，我们还是以数组 arr = [5,1,4,2,8,4] 为例进行一趟归并排序。

第一步：计算数组的中间元素，然后将数组分成和两个区间，即与两个子数组，这一步属于「分」的过程。

第二步：计算分出来的子数组的中间元素， 1 ，将数组分成了以及两个子数组，这一同样是「分」的过程，但同时也应该注意到，这一步和第一步的操作过程是一致的，也就说第一步和第二步是同一个功能，所以最终你会在代码中看到递归实现，后面会专门讲归并排序所蕴含的递归思想。

第三步：将上一步分出的子数组 [0,1] 再进行拆分， , 将数组分成了 [0] 和 [1]，只包含一个元素。

第四步：将 arr[0] 和 arr[1] 进行合并，因为上一步得到的两个数组不可再分了，已经有序，所以进行合并。这一步事实上也是「治」的过程，所谓治就是真正进行排序的过程，因为通过这一步元素 5 和 1 的顺序将被改变。

「归并排序」之归与并，分与治？之后的每一步都是如此，我们在下图中将每一步用红色数字标注了出来：

分治和递归就像一对好基友，永远不分离，为了看到归并排序的递归过程，我们先看一下归并排序的实现。

实现代码

归并排序包含两个过程，分和治，所以递归实现代码也相当简单。

void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) { 
        // 计算 l 和 r 的中点
        int m = (l + r) / 2; 

        // 对 分 出的两个子数组分别进行归并排序 
        mergeSort(arr, l, m); 
        mergeSort(arr, m + 1, r); 

        // 合并有序的两部分
        merge(arr, l, m, r); 
    } 
}

和之前讲插入排序的递归实现一样，我们将数组 arr = [5,1,4,2,8,4] 带入代码中：

心中一惊，为何这里的递归过程如此曲折，事实上没有什么可担心的，你将代码中的 mergeSort(arr,l,r) 理解为「分」和「递」，而将 merge(arr,l,m,r) 理解为「治」和「归」，心中就会豁然开朗，递归与分治就是孪生兄弟。

那么，「治」和「归」的过程到底又是如何实现的呢？

不急，我们以最后一次 merge(arr,0,2,5) 操作为栗子说明一下。

最后一次合并前的数组如下所示：

此时原始数组已被分成了两个有序的子数组 [1,4,5] 和 [2,4,8] .

紧接着将两个有序的子数组分别保存到一个数组 L[]=[1,4,5] 和 R[]=[2,4,8] 当中：「归并排序」之归与并，分与治？

然后再将这个子数组 L[] 和 R[] 合并到原始数组当中：

治（也就是合并）的代码实现：

void merge(int arr[], int l, int m, int r) 
{ 
    // 计算合并的两个子数组的大小
    int n1 = m - l + 1; 
    int n2 = r - m; 

    /*创建两个临时的子数组，存储要合并的两个子数组 */
    int L[] = new int[n1]; 
    int R[] = new int[n2]; 
    
    /*拷贝数据*/
    for (int i = 0; i < n1; ++i) 
        L[i] = arr[l + i]; 
    for (int j = 0; j < n2; ++j) 
        R[j] = arr[m + 1 + j]; 

    /* 合并临时数组 */
    // 初始化两个临时子数组的下标
    int i = 0, j = 0; 

    // 初始化合并后数组的下标k为 l(不是1，是left)
    int k = l; 
    while (i < n1 && j < n2) { 
        if (L[i] <= R[j]) { 
            arr[k] = L[i]; 
            i++; 
        } 
        else { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
    /* 如果 L[] 有剩余，拷贝 */
    while (i < n1) { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
    /* 拷贝 R[] 中剩余的部分 */
    while (j < n2) { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
}

复杂度分析

时间复杂度

归并排序（二路归并）方法就是把一个包含 n 个数的数组，折半拆分为两个子数组（二路），然后再将这两个子数组再分，一直分下去，直到分为n个长度为1的元素。然后两两按大小归并。如此反复，直到最后形成包含 n 个数的一个有序数组。

归并排序总时间 = 拆分时间 + 子数组排好序时间 + 合并时间

无论每个数组有多少个数都是折半拆分，也就是代码中的 int m = (l + r) / 2;，所以拆分时间就是个常数，可以忽略不计。

则：归并排序总时间 = 子数组排序时间 + 合并时间

假设对于一个包含 n 个元素的数组而言排序时间为 .

将包含 n 个元素的数组拆分成 2 个分别包含的子数组，则归并排序的时间为，其中的表示合并时间，也就是 merge() 函数中合并两个子数组的时间，因为合并两个子数组总体就涉及到一个 while 循环，时间复杂度为 .

继续将两个分别拆分为的子数组，此时归并排序的时间为

这里的如何得来的呢？

已知，其中表示一个包含个元素的数组排好序的时间，n表示合并两个个元素的子数组所用的时间。

而包含个元素的子数组的排序时间 = 包含个元素的两个子数组排好序的时间 + 合并两个包含的元素得到的合并时间，即：

将与之间的关系式带入当中，就是将所有的替换为：

则，，注意

同样的道理可以推知与之间的关系：，注意

以此类推...

可以推知与之间的关系：

∴ 归并排序的时间复杂度为量级。

空间复杂度

在合并的时候，我们使用了存储待合并的两个数组元素的空间，这个数组大小依次开辟的就是 1，2，4，8，...，n/2，但是开辟了两个，所以可能开辟的空间大小为 2，4，8，......，n，归并排序的空间复杂度为量级。与插入排序，冒泡排序，还有选择排序相比，你也可以将归并排序理解为空间换时间的有效例证。归并排序也就不是一个原地排序算法了，原地排序算法的空间复杂度为 .

稳定性分析

这幅图中，可以看到归并排序是稳定的排序算法，排序前后，数组中两个4的相对位置没有发生变化。归并排序稳定的根本原因在合并的时候对值相同的两个关键字不存在交换的可能性。

归并排序相关问题摘要

关于归并排序的问题还有很多，下面给大家列举一些，之后的文章中都会一一向大家介绍。

与数组相比，归并排序在单链表上进行排序的优势何在？
如何实现一个空间复杂度为，时间复杂度为的归并排序？
三路归并排序如何实现和操作？
如何让今天讲的归并排序变成一个原地排序算法（In-place Algorithm)？
迭代形式的归并排序又该如何实现？
如何利用统计一个数组中次序颠倒的元素对的个数，比如 arr[] = [3,1,2] ,就应该返回 2，因为 (3,1) , (3,2) 都是次序相反的数对。

还有更多关于排序算法的题目和讲解景禹都会努力在排序算法专题分享给大家，最近工作还有接了一个私活，更新文章有些晚了，还望各位见谅，谢谢你们一直以来的关注和鼓励~~

vlambda博客
学习文章列表