vlambda博客
学习文章列表

大家好，我是梁唐。

今天我们继续聊聊《算法-第四版》这本书，我们继续排序相关的话题。

在上一篇文章当中我们复习了希尔排序的原理，希尔排序的复杂度虽然突破了 ，但依然不低。在大型数据上的表现依然很差，所以计算学家们又马不停蹄地继续研究起了新的排序算法。

当尝试着将分而治之的思想应用在排序上之后，人们惊人地发现算法的复杂度相比于从前有了一个质的提升。这种使用分治归并思想创建的算法，被称为归并排序（merge sort）。

归并排序在各大公司的面试当中经常出现，一般都是以白板编程的形式。老梁之前在面试BAT的时候就遇到过，并且归并排序的代码非常nice，反复多写几次也有助于提升编码能力。

归并操作

在讲解归并排序算法地整个原理之前，需要先理解什么是归并。

归并操作的原理其实很简单，只有一句话：即将两个有序的数组合并在一起。由于两个数组本身有序，我们可以在 的复杂度内完成这一操作。

我们举个例子：

a = [1, 4, 6]
b = [2, 4, 5]
c = []

我们用i和j分别表示a和b两个数组的下标，c表示归并之后的数组，显然一开始的时候i, j = 0, 0。我们不停地比较a和b数组i和j位置大小关系，将小的那个数填入c。

填入一个数之后：

i = 1
j = 0
a = [1, 4, 6]
b = [2, 4, 5]
c = [1]

填入两个数之后：

i = 1
j = 1
a = [1, 4, 6]
b = [2, 4, 5]
c = [1, 2]

我们重复以上步骤，直到a和b数组当中所有的数都填入c数组为止，我们可以很方便地写出以上操作的代码：

void merge(vector<int>& a, vector<int>& b, vector<int> &c) {
  int n = a.size(), m = b.size();
 int i = 0, j = 0;
  while (i < n || j < m) {
    if (i == n) {
      c.push_back(b[j++]);
    }
    if (j == m) {
      c.push_back(a[i++]);
    }
    if (a[i] <= b[j]) c.push_back(a[i++]);
    else c.push_back(b[j++]);
  }
}

这段代码还是有点复杂的，因为我们在插入元素的时候还需要考虑数组越界的问题。所以需要写很多的判断。

对于这个问题，我们有一个常用的优化，就是给a和b两个数组的末尾插入一个极大值作为“标兵”。有了这个近乎于无穷大的标兵守在最后，就可以保证在循环结束之前不会出现数组越界的问题。

如此就可以简化很多代码了（前提，a和b数组当中不存在和标兵一样大的数）。

我们来看代码：

void merge(vector<int>& a, vector<int>& b, vector<int> &c) {
  int n = a.size(), m = b.size();
 int i = 0, j = 0;
  a.push_back(INT_MAX);
  b.push_back(INT_MAX);
  
  while (i < n || j < m) {
    if (a[i] <= b[j]) c.push_back(a[i++]);
    else c.push_back(b[j++]);
  }
}

归并排序

理解了归并操作之后，接下来要做的就是使用归并操作来完成排序了。

我们带着归并操作往排序这个目标上靠来进行反推：我们需要整个数组有序，可以先将数组一分为二，先让这两个子数组有序。这两个子数组有序了之后，我们只需要进行一次归并，就可以得到完整有序的数组了。

但问题又来了，我们怎么保证子数组也有序呢？虽然理解了归并操作，但似乎距离完成排序依然很远。

表面上看的确如此，但数组有序性这个概念里面有一个bug，就是当数组当中只有一个元素的时候，它就是天然有序的。

所以我们可以将数组一直往下拆分，直到数组当中只有一个元素为止。这样它们就都是有序的了，我们再反向一层层归并，直到整个数组有序。

我们举个例子：

          [4, 1, 3, 2]
           /        \
        [4, 1]    [3, 2]
        /    \    /    \
      [4]   [1]  [3]   [2]   # 每个元素单独成为一个数组，有序
        \    /     \   /
        [1, 4]     [2, 3]
           \        /
          [1, 2, 3, 4]

通过上面的这个过程我们可以发现，在归并排序的时候，我们先一直往下递归切分数组，直到所有的切片当中只有一个元素天然有序。接着一层一层地归并回来，当所有元素归并结束的时候，数组就完成了排序。这也就是归并排序的全部过程。

如果还不理解，还可以参考一下下面的动图。

‍最后，我们完整地将整个算法用代码实现一遍。

这里我们先来使用比较简单的Python，因为Python可以使用数组切片等许多操作，因此编码上会简单许多。

def merge_sort(arr):
    n = len(arr)
    # 当长度小于等于1，说明天然有序
    if n <= 1:
        return arr
    mid = n // 2
    # 通过切片将数组一分为二，递归排序左边以及右边部分
    L, R = merge_sort(arr[: mid]), merge_sort(arr[mid: ])
    n_l, n_r = len(L), len(R)

    # 数组当中插入标兵
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    new_arr = []
    i, j = 0, 0

    # 归并已经排好序的L和R
    while i < n_l or j < n_r:
        if L[i] <= R[j]:
            new_arr.append(L[i])
            i += 1
        else:
            new_arr.append(R[j])
            j += 1
    return new_arr

最后我们再来看一下C++版本：

void merge(vector<int>& res, vector<int>& l, vector<int> &r) {
    int n = l.size(), m = r.size();
    int i = 0, j = 0;
    l.push_back(INT_MAX);
    r.push_back(INT_MAX);

    while (i < n || j < m) {
        if (l[i] < r[j]) res.push_back(l[i++]);
        else res.push_back(r[j++]);
    }
}

void merge_sort(vector<int>& nums) {
    if (nums.size() <= 1) return ;
    int m = nums.size() / 2;

    vector<int> lef(nums.begin(), nums.begin() + m);
    vector<int> rig(nums.begin()+m, nums.end());
    merge_sort(lef);
    merge_sort(rig);
    nums.clear();
    merge(nums, lef, rig);
}

和Python版本相比稍稍复杂了一些，但只要理解了归并和排序的方法，也并不难懂。不妨试着多写几次，很快就能熟练掌握的。

好了，关于归并排序这个话题就先聊到这里，感谢大家的阅读。