面试官：手写归并排序、快排能做到吗？我：小case！

作者 | 梁唐

大家好，我是梁唐。

在之前的文章当中，我们通过海盗分金币问题详细讲解了递归这个方法。

我们可以认为在递归的过程当中，我们通过函数自己调用自己，将大问题转化成了小问题，因此简化了编码以及建模。

递归这一思想至关重要，因为很多算法都是基于递归展开的。其中最经典的就是分治算法，应该算是递归这一思想最经典的应用，也是面试中的常客。

而分治算法当中的经典应用就是归并排序以及快速排序这两大排序算法，所以今天我们就一起来深入探讨一下这两个排序算法。从它们理解分治算法，再反过来加深对递归这一思想的理解。好了，我们废话不多说，开始进入正题吧。

归并排序

归并排序的代码看起来有些复杂，其实它的思路非常简单，它的核心原理只有一句话：将两个有序数组归并在一起的复杂度为

归并操作

所谓归并，也就是把两个有序数组里的元素合并在到同一个数组当中，并且保持数组的有序性。

我们举个例子，假设我们有两个数组a和b，我们要把它们当中的元素都放入数组c当中，并且还要保证数组c中的元素依然是有序的。

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

我们用i和j分别表示a和b两个数组的下标，一开始的时候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数组为止。

关于这个操作的代码非常容易写，我这里提供一个Python版本的。主要是Python的代码和伪代码比较接近，比较容易理解。

def merge(a, b):
  i, j = 0, 0
  c = []
  while i < len(a) or j < len(b):
    # 判断a数组是否已经全部放入
    if i == len(a):
      c.append(b[j])
      j += 1
      continue
    elif j == len(b):
      c.append(a[i])
      i += 1
      continue
    # 判断大小
    if a[i] <= b[j]:
      c.append(a[i])
      i += 1
    else:
      c.append(b[j])
      j += 1
  return c

从上面的代码我们也能看出来，这个过程虽然简单，但是写起来还是有点麻烦的。

因为我们还需要判断a和b是否为空，这里有一个简化代码的优化，就是在a和b两个数组当中插入一个极大值作为“标兵”。

这个标兵设置成正无穷大的数，这样当a数组当中其他元素都弹出之后。由于标兵大于b数组当中除了标兵之外其他所有的数，就可以保证a数组永远不会越界，如此就可以简化很多代码了（前提，a和b数组当中不存在和标兵一样大的数）。

我们来看简化之后的代码：

def merge(a, b):
  i, j = 0, 0
  # 插入标兵
  a.append(MAXINT)
  b.append(MAXINT)
  c = []
  # 由于插入了标兵，所以长度判断的时候需要-1
  while i < len(a)-1 or j < len(b)-1:
    if a[i] <= b[j]:
      c.append(a[i])
      i += 1
    else:
      c.append(b[j])
      j += 1
  return c

排序操作

归并操作很好理解，接下来的问题是我们怎么利用归并数组的操作来排序呢？

自己想可能不一定想得出来，但只要我们利用上递归的思想其实很简单。

这里我们不妨来思考一下归并的逆操作，我们要让完整的数组有序，首先需要将这个数组一分为二，这两个部分都各自有序。

一分为二之后，我们化零为整，把其中的一个部分看成是整体，再使用同样的方法继续一分为二。这样一直拆分下去，直到最后拆分之后的数组只剩下一个元素，由于单个元素的数组是天然有序的。所以就满足了归并操作的条件了，这时候我们再一层层归并回来，化零为整，得到完整的有序数组。

我这样说可能有些枯燥，不妨来看一个例子。

          [4, 1, 3, 2]
           /        \
        [4, 1]    [3, 2]
        /    \    /    \
      [4]   [1]  [3]   [2]
        \    /     \   /
        [1, 4]     [2, 3]
           \        /
          [1, 2, 3, 4]

我们首先把[4, 1, 3 ,2]这个数组一分为二，得到[4, 1]和[3, 2]。我们把[4, 1]看成是完整的数组再继续拆分，得到[4]和[1]。这两个数组里都只有一个元素，天然有序，所以就可以使用归并操作了。归并之后得到[1, 4]，再和[3, 2]同样操作之后得到的[2, 3]归并，这样一层层归并回来，就得到了有序的[1, 2, 3, 4]了。

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

最后，我们来试着用代码来实现。

之前我曾经在面试的时候被要求在白板上写过归并排序，当时我用的C++觉得编码还有一定的难度。现在，当我用习惯了Python之后，我感觉编码难度降低了很多。因为Python支持许多数组相关的高级操作，比如切片，变长等等。整个归并排序的代码不超过20行，我们一起来看下代码：

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

代码很简单，但是理解起来对于新手来说可能还是有点难。这里的关键点在于对递归的认识和理解，对于初学者我们可以忘记递归这回事，就把自身这个函数看成是一个独立的函数，先忘记它是我们编写的，只需要关注它的输入和输出，利用它的输出完成我们想要的操作。

比如在这段代码当中merge_sort函数可以完成一个数组的排序，虽然这个函数是我们编写的，但是我们可以先假设它已经开发好了，可以实现排序了。所以我们直接把数组一分为二，然后分别调用merge_sort就得到了两个有序的子数组了。

得到两个有序的子数组之后，我们要做的就剩下很简单的归并操作了。大家可以对比一下，归并排序的代码和归并这个操作的代码非常非常地相似，唯一的差别就在于归并排序当中多了递归调用的部分。

归并排序是用来理解递归以及理解分治这个思想非常好的例子，建议新手多写几遍多多练习。

快速排序

快速排序同样利用了分治的思想，我们每次做一个小的操作，让数组的一部分变得有序，之后我们通过递归，将这些有序的部分组合在一起，达到整体有序。

在归并排序当中，我们划分问题的方法是横向切分，我们直接将数组一分为二，针对这两个部分分别排序。

快排稍稍不同，它并不是针对数组的横向切分，而是从问题本身出发的“纵向”切分。在快速排序当中，我们解决的子问题不是对数组的一部分排序，而是提升数组的有序程度。

怎么提升呢？快排的做法非常巧妙，首先会在数组当中寻找一个数，作为标杆。然后，我们利用这个标杆调整数组当中元素的顺序。将小于它的放到它的左侧，大于它的放到它的右侧。这么一个操作结束之后，可以肯定的是，对于我们选定的标杆来说，它所在的位置就是排序之后它应该在的位置。

我们来看个例子：

a = [8, 4, 3, 9, 10, 2, 7]

我们选择7作为标杆，一轮操作之后可以得到：

a = [2, 4, 3, 7, 9, 10, 8]

接着我们怎么做呢？很简单，我们只需要针对标杆前面以及标杆后面的部分重复上述操作即可。如果还不明白的同学可以看一下下面这张动图：

如果用C++写过快排的同学肯定对于快排的代码印象深刻，它是属于典型的原理不难，但是写起来很麻烦的算法。因为快速排序需要用到两个下标，写的时候一不小心很容易写出bug。

同样，由于Python当中动态数组的支持非常好，我们可以避免使用下标来实现快排，这样代码的可读性以及编码难度都要降低很多。

多说无益，我们来看代码：

def quick_sort(arr):
    n = len(arr)
    # 长度小于等于1说明天然有序
    if n <= 1:
        return arr
  
    # pop出最后一个元素作为标杆
    mark = arr.pop()
    # 用less和greater分别存储比mark小或者大的数
    less, greater = [], []
    for x in arr:
        if x <= mark:
            less.append(x)
        else:
            greater.append(x)
    arr.append(mark)
    return quick_sort(less) + [mark] + quick_sort(greater)

整个代码出去注释，不到15行，我想大家应该都非常容易理解。

最后，我们来分析一下这两个算法的复杂度，为什么说这两个算法都是

的算法呢？（不考虑快速排序最差情况）这个证明非常简单，我们放一张图大家一看就明白了：

上图是一张递归树的展开图，无论是归并排序还是快速排序，在递归当中我们都遍历了整个数组的元素一次，所以复杂度是

虽然随着递归层数的加深，我们把完整的数组也进行了一层层的拆分。但是横向来看，所有拆分之后的子问题的元素之和仍然是n。所以每一层的遍历的复杂度仍然是O(n) ，这里的n指的是总元素的个数。

所以整个问题的复杂度就是n乘上拆分的层数，我们知道每一次都将数组一分为二。对于长度为n的数组来说，最多可以拆分\log_2 n

次，那么整体的复杂度就是O(n \log _2 n) ，忽略底数的话可以写成O(n\log n) 。

当然对于快速排序算法来说，如果数组是倒序的，我们默认取最后一个元素作为标杆的话，我们是无法均分数组的，因为除标杆之外所有的元素都比它大。在这种情况下算法的复杂度会退化到n^2 。所以我们说快速排序算法最差复杂度是O(n^2)。

到这里，关于归并排序与快速排序的算法就讲完了。这两个算法并不难，我想学过算法和数据结构的同学应该都有印象，但是在实际面试当中，真正能把代码写出来并且没有明显bug的实在是不多。我想，不论之前是否已经学会了，回顾一下都是很有必要的吧。