排序算法系列之（七）——分分合合的归并排序

发表于 | 更新于 | 分类于 |
热度 ℃   |   字数统计: 2,796(字)   |   阅读时长: 12(分) |

前言

再一次总结基础的排序算法，印象里距离上一次总结排序也没过多久，查询后才发现上一篇总结《排序算法系列之（六）——逐步砍掉树杈的堆排序》到现在已经过去了3年多的时间，真是时光荏苒，岁月如梭啊，这次想起总结排序起因并不是排序，而是查找逆序数对，而解决逆序数对通常使用的两种方式是归并排序和离散化树状数组，所以我又把归并排序捡起来了

归并排序

温故而知新，知识有时候就是这么神奇，多年以后再次看到归并排序，才发现以前掌握的归并排序并不全面，之前理解的归并排序主要放在“并”这个操作，但是其实归并排序中还有很重要的一环，那就是“分”，先分后合才是完整的归并排序。

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用，首先将整个序列一分为二得到两个序列，然后将分出的两个序列排好序后再合并，得到完全有序的序列。对于子序列如果元素大于1则继续进行一分为二，分别排序再合并的操作，直至有序，算法本身是通过一个递归的概念定义。当然反过来通过递推也可以实现，相邻区间两两合并，最终至全部有序也是可以的。

提到一分为二很容易联想到快速排序，在最优的情况下待排序的数组每次被一分为二，将小于中间值的元素全部移到数组前半段，将大于中间值的元素全部移到数组后半段，完成一趟快排，然后对每段分别采用相同的策略从而达到整理有序，这是快排的思想，听起来有些部分确实和归并排序很像，但是区别也是很大的，比如快排不需要合并的操作，另外快排是一种不稳定的排序。

为了简单一点，我们还是采用递归的版本来描述一下归并排序，先画一个图，直观的看下归并排序中二分天下是怎么操作的，先分裂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph TB
    A[2,3,9,4,7,12,6,1,11,5]-->B[2,3,9,4,7];
    A[2,3,9,4,7,12,6,1,11,5]-->C[12,6,1,11,5];
    B[2,3,9,4,7]-->D[2,3,9];
    B[2,3,9,4,7]-->E[4,7];
    C[12,6,1,11,5]-->F[12,6,1];
    C[12,6,1,11,5]-->G[11,5];
    D[2,3,9]-->H[2,3];
    D[2,3,9]-->I[9];
    E[4,7]-->J[4];
    E[4,7]-->K[7];
    F[12,6,1]-->L[12,6];
    F[12,6,1]-->M[1];
    G[11,5]-->N[11];
    G[11,5]-->O[5];
    H[2,3]-->P[2];
    H[2,3]-->Q[3];
    L[12,6]-->R[12];
    L[12,6]-->S[6];
idx_0 idx_1 idx_2 idx_3 idx_4 idx_5 idx_6 idx_7 idx_8 idx_9
2 3 9 4 7 12 6 1 11 5

排序后再合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph BT
    A[1,2,3,4,5,6,7,9,11,12]-->B[2,3,4,7,9];
    A[1,2,3,4,5,6,7,9,11,12]-->C[1,5,6,11,12];
    B[2,3,4,7,9]-->D[2,3,9];
    B[2,3,4,7,9]-->E[4,7];
    C[1,5,6,11,12]-->F[1,6,12];
    C[1,5,6,11,12]-->G[5,11];
    D[2,3,9]-->H[2,3];
    D[2,3,9]-->I[9];
    E[4,7]-->J[4];
    E[4,7]-->K[7];
    F[1,6,12]-->L[6,12];
    F[1,6,12]-->M[1];
    G[11,5]-->N[11];
    G[11,5]-->O[5];
    H[2,3]-->P[2];
    H[2,3]-->Q[3];
    L[6,12]-->R[12];
    L[6,12]-->S[6];

排序过程

上面的图可以很清楚的看出怎样划分以及合并的结果，但是对于描述怎样每个子数组怎样从无序变成有序不太明显，同时也忽略了合并的算法，所以下面用语言简单描述下，其实每个子数组怎样从无序变成有序这个并不需要关心，因为数组是一个元素是必定有序，当数组包含两个元素时，说明它是由两个单元素数组“归并”而成，所以我们需要掌握的是归并的算法。同理，4个元素的数组是由两个双元素有序数组归并而成，同样说明需要掌握的只有归并的逻辑。

下面我们具体操作一下，以 [2,3,4,7,9] 和 [1,5,6,11,12] 两个子数组归并成最终有序数组为例，模拟一次从小到大排序。

首先我们假设有两个指针L 和 R 分别指向两个数组的首个元素，另有一个数组 M 为结果数组，初始为空 M = []，下面开始操作，初始数据如下：

1
2
3
[2(L),3,4,7,9]
[1(R),5,6,11,12]
[]
  1. 比较两个指针元素，找出两个指针所指的更小的元素，放入结果数组后指针加一，R 指针元素更小，元素1放入结果数组，指针向后加一
1
2
3
[2(L),3,4,7,9]
[1,5(R),6,11,12]
[1]
  1. 继续步骤1，这次 L 指针元素更小，元素2放入结果数组，指针向后加一
1
2
3
[2,3(L),4,7,9]
[1,5(R),6,11,12]
[1,2]
  1. 继续比较，还是 L 指针元素更小，元素3放入结果数组，指针向后移动
1
2
3
[2,3,4(L),7,9]
[1,5(R),6,11,12]
[1,2,3]
  1. 继续比较，仍然是 L 指针元素更小，元素4放入结果数组，指针向后移动
1
2
3
[2,3,4,7(L),9]
[1,5(R),6,11,12]
[1,2,3,4]
  1. 继续比较，这次变成 R 指针元素更小，元素5放入结果数组，指针向后移动
1
2
3
[2,3,4,7(L),9]
[1,5,6(R),11,12]
[1,2,3,4,5]
  1. 继续比较，仍然是 R 指针元素更小，元素6放入结果数组，指针向后移动
1
2
3
[2,3,4,7(L),9]
[1,5,6,11(R),12]
[1,2,3,4,5,6]
  1. 继续比较，现在是 L 指针元素更小，元素7放入结果数组，指针向后移动
1
2
3
[2,3,4,7,9(L)]
[1,5,6,11(R),12]
[1,2,3,4,5,6,7]
  1. 继续比较，仍是 L 指针元素更小，元素9放入结果数组，指针向后移动
1
2
3
[2,3,4,7,9](L)
[1,5,6,11(R),12]
[1,2,3,4,5,6,7,9]
  1. 现在 L 指针已经走到了数组的最后，而 R 所在的数组还有元素，说明 R 中剩余的元素肯定都比 L 最后一个元素都大，所以直接把 R 中剩余元素11和12放到结果数组就完成了排序
1
2
3
[2,3,4,7,9](L)
[1,5,6,11,12](R)
[1,2,3,4,5,6,7,9,11,12]

从排序过程也可以看出，使用归并排序需要一个额外的结果数组来完成合并操作，下面我们用代码来实现一下这个算法。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/*
功能：  交换两个变量
参数：  element1--被交换的第一个元素的地址
       element2--被交换的第二个元素的地址
返回值：无
注意： 只用来表示思路，不考虑指针为空等特殊情况
*/
void swap_data(int* element1, int* element2)
{
    int middle_value = *element1;
    *element1 = *element2;
    *element2 = middle_value;
}

/*
功能：  将数组的两个有序段[left,mid]和[mid+1,right]合并成[left,right]区间完整有序
参数：  array--表示待排序的数组，此处会退化成指针
        left--数组第一段开始的索引
        mid--数组第一段结束的索引
        right--数组第二段结束的索引
返回值：无
注意： 只用来表示思路，不考虑指针为空等特殊情况
*/
void merge(int array[], int left, int mid, int right)
{
    int* temp = (int*)malloc((right-left+1)*4);
    int i = 0, l = left, r = mid + 1;

    while (l <= mid && r <= right)
    {
        if (array[l] <= array[r])
            temp[i++] = array[l++];
        else
            temp[i++] = array[r++];
    }

    //第一段仍有元素没加到结果
    while (l <= mid) temp[i++] = array[l++];

    //第二段仍有元素没加到结果
    while (r <= right) temp[i++] = array[r++];

    //结果赋值回原数组
    for (int j = 0; j <= right - left; j++) array[left+j] = temp[j];

    free(temp);
}

/*
功能：  归并排序，实现数组元素从小到大排列
参数：  array--表示待排序的数组，此处会退化成指针
        left--数组第一个待排序元素索引
        right--数组最后一个待排序元素索引
返回值：无
注意： 只用来表示思路，不考虑指针为空等特殊情况
*/
void merge_sort(int array[], int left, int right)
{
    if (right > left)
    {
        int mid = (right + left) / 2;
        merge_sort(array, left, mid);
        merge_sort(array, mid+1, right);
        merge(array, left, mid, right);
    }
}

代码分析

归并排序的核心的是分割和归并，分割时采取递归一分为二就可以，然后归并才是体现算法精髓的地方，合并时通常使用两个指针来分别指向数组的两段，通过不断比较元素大小将两段有序数组合并成一段，在排序过程中使用了额外的空间，这也是归并排序的劣势，例子中为了方便每次合并时都申请了新数组，其实可以优化一下，在排序开始申请一个临时数组就可以，中间合并时使用同一个临时数组就可以。

运行测试

在线编辑器是一个很方便的测试代码的环境，如果想本地调试一下，也可以直接下载归并排序–源码，在本地编译后进行调试，其实边看代码边调试是理解算法思路很有效的方式。

总结

  • 归并排序的核心思想是不断二分后合并两段有序子数组达到最终有序
  • 归并排序因为是优先比较相邻的元素，所以是稳定的排序算法
  • 归并排序使用了临时空间，最大与原数组等长，优化时可以在排序前申请一个就可以服务于整个排序过程
==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

生活的点点滴滴随时间流淌，它们不是逝去，恰恰是它们组成了我们的生活，我们可以选择躺平，可以选择奋斗，可以选择全力以赴，当我们还可以选择的时候，请感恩你所拥有的一切吧，特别是对已经攥在手里的东西，深深地表达一下感激，勿等失去徒伤悲。

2022-10-4 02:20:05

Albert Shi wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客