[[407867]]

大家好，我是梁唐。

在之前的文章當中，我們通過海盜分金幣問題詳細講解了遞歸這個方法。

我們可以認為在遞歸的過程當中，我們通過函數自己調用自己，將大問題轉化成了小問題，因此簡化了編碼以及建模。

遞歸這一思想至關重要，因為很多算法都是基于遞歸展開的。其中最經典的就是分治算法，應該算是遞歸這一思想最經典的應用，也是面試中的常客。

而分治算法當中的經典應用就是歸并排序以及快速排序這兩大排序算法，所以今天我們就一起來深入探討一下這兩個排序算法。從它們理解分治算法，再反過來加深對遞歸這一思想的理解。好了，我們廢話不多說，開始進入正題吧。

歸并排序

歸并排序的代碼看起來有些復雜，其實它的思路非常簡單，它的核心原理只有一句話：將兩個有序數組歸并在一起的復雜度為。

歸并操作

所謂歸并，也就是把兩個有序數組里的元素合并在到同一個數組當中，并且保持數組的有序性。

我們舉個例子，假設我們有兩個數組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。所以每一層的遍歷的復雜度仍然是

，這里的n指的是總元素的個數。

所以整個問題的復雜度就是n乘上拆分的層數，我們知道每一次都將數組一分為二。對于長度為n的數組來說，最多可以拆分次，那么整體的復雜度就是

，忽略底數的話可以寫成。

當然對于快速排序算法來說，如果數組是倒序的，我們默認取最后一個元素作為標桿的話，我們是無法均分數組的，因為除標桿之外所有的元素都比它大。在這種情況下算法的復雜度會退化到。所以我們說快速排序算法最差復雜度是。

到這里，關于歸并排序與快速排序的算法就講完了。這兩個算法并不難，我想學過算法和數據結構的同學應該都有印象，但是在實際面試當中，真正能把代碼寫出來并且沒有明顯bug的實在是不多。我想，不論之前是否已經學會了，回顧一下都是很有必要的吧。

本文轉載自微信公眾號「Coder梁」，可以通過以下二維碼關注。轉載本文請聯系Coder梁公眾號。