[[407867]]

大家好，我是梁唐。

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

我們可以認(rèn)為在遞歸的過程當(dāng)中，我們通過函數(shù)自己調(diào)用自己，將大問題轉(zhuǎn)化成了小問題，因此簡化了編碼以及建模。

遞歸這一思想至關(guān)重要，因為很多算法都是基于遞歸展開的。其中最經(jīng)典的就是分治算法，應(yīng)該算是遞歸這一思想最經(jīng)典的應(yīng)用，也是面試中的?？?。

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

歸并排序

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

歸并操作

所謂歸并，也就是把兩個有序數(shù)組里的元素合并在到同一個數(shù)組當(dāng)中，并且保持?jǐn)?shù)組的有序性。

我們舉個例子，假設(shè)我們有兩個數(shù)組a和b，我們要把它們當(dāng)中的元素都放入數(shù)組c當(dāng)中，并且還要保證數(shù)組c中的元素依然是有序的。

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

我們用i和j分別表示a和b兩個數(shù)組的下標(biāo)，一開始的時候i, j = 0, 0。我們不停地比較a和b數(shù)組i和j位置大小關(guān)系，將小的那個數(shù)填入c。

填入一個數(shù)之后：

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

填入兩個數(shù)之后：

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

我們重復(fù)以上步驟，直到a和b數(shù)組當(dāng)中所有的數(shù)都填入c數(shù)組為止。

關(guān)于這個操作的代碼非常容易寫，我這里提供一個Python版本的。主要是Python的代碼和偽代碼比較接近，比較容易理解。

def merge(a, b): 
  i, j = 0, 0 
  c = [] 
  while i < len(a) or j < len(b): 
    # 判斷a數(shù)組是否已經(jīng)全部放入 
    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是否為空，這里有一個簡化代碼的優(yōu)化，就是在a和b兩個數(shù)組當(dāng)中插入一個極大值作為“標(biāo)兵”。

這個標(biāo)兵設(shè)置成正無窮大的數(shù)，這樣當(dāng)a數(shù)組當(dāng)中其他元素都彈出之后。由于標(biāo)兵大于b數(shù)組當(dāng)中除了標(biāo)兵之外其他所有的數(shù)，就可以保證a數(shù)組永遠不會越界，如此就可以簡化很多代碼了(前提，a和b數(shù)組當(dāng)中不存在和標(biāo)兵一樣大的數(shù))。

我們來看簡化之后的代碼：

def merge(a, b): 
  i, j = 0, 0 
  # 插入標(biāo)兵 
  a.append(MAXINT) 
  b.append(MAXINT) 
  c = [] 
  # 由于插入了標(biāo)兵，所以長度判斷的時候需要-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 

排序操作

歸并操作很好理解，接下來的問題是我們怎么利用歸并數(shù)組的操作來排序呢?

自己想可能不一定想得出來，但只要我們利用上遞歸的思想其實很簡單。

這里我們不妨來思考一下歸并的逆操作，我們要讓完整的數(shù)組有序，首先需要將這個數(shù)組一分為二，這兩個部分都各自有序。

一分為二之后，我們化零為整，把其中的一個部分看成是整體，再使用同樣的方法繼續(xù)一分為二。這樣一直拆分下去，直到最后拆分之后的數(shù)組只剩下一個元素，由于單個元素的數(shù)組是天然有序的。所以就滿足了歸并操作的條件了，這時候我們再一層層歸并回來，化零為整，得到完整的有序數(shù)組。

我這樣說可能有些枯燥，不妨來看一個例子。

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

我們首先把[4, 1, 3 ,2]這個數(shù)組一分為二，得到[4, 1]和[3, 2]。我們把[4, 1]看成是完整的數(shù)組再繼續(xù)拆分，得到[4]和[1]。這兩個數(shù)組里都只有一個元素，天然有序，所以就可以使用歸并操作了。歸并之后得到[1, 4]，再和[3, 2]同樣操作之后得到的[2, 3]歸并，這樣一層層歸并回來，就得到了有序的[1, 2, 3, 4]了。

如果還不理解，還可以參考一下下面的動圖。

最后，我們來試著用代碼來實現(xiàn)。

之前我曾經(jīng)在面試的時候被要求在白板上寫過歸并排序，當(dāng)時我用的C++覺得編碼還有一定的難度?，F(xiàn)在，當(dāng)我用習(xí)慣了Python之后，我感覺編碼難度降低了很多。因為Python支持許多數(shù)組相關(guān)的高級操作，比如切片，變長等等。整個歸并排序的代碼不超過20行，我們一起來看下代碼：

def merge_sort(arr): 
    n = len(arr) 
    # 當(dāng)長度小于等于1，說明天然有序 
    if n <= 1: 
        return arr 
    mid = n // 2 
    # 通過切片將數(shù)組一分為二，遞歸排序左邊以及右邊部分 
    L, R = merge_sort(arr[: mid]), merge_sort(arr[mid: ]) 
    n_l, n_r = len(L), len(R) 
 
    # 數(shù)組當(dāng)中插入標(biāo)兵 
    L.append(sys.maxsize) 
    R.append(sys.maxsize) 
    new_arr = [] 
    i, j = 0, 0 
 
    # 歸并已經(jīng)排好序的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 

代碼很簡單，但是理解起來對于新手來說可能還是有點難。這里的關(guān)鍵點在于對遞歸的認(rèn)識和理解，對于初學(xué)者我們可以忘記遞歸這回事，就把自身這個函數(shù)看成是一個獨立的函數(shù)，先忘記它是我們編寫的，只需要關(guān)注它的輸入和輸出，利用它的輸出完成我們想要的操作。

比如在這段代碼當(dāng)中merge_sort函數(shù)可以完成一個數(shù)組的排序，雖然這個函數(shù)是我們編寫的，但是我們可以先假設(shè)它已經(jīng)開發(fā)好了，可以實現(xiàn)排序了。所以我們直接把數(shù)組一分為二，然后分別調(diào)用merge_sort就得到了兩個有序的子數(shù)組了。

得到兩個有序的子數(shù)組之后，我們要做的就剩下很簡單的歸并操作了。大家可以對比一下，歸并排序的代碼和歸并這個操作的代碼非常非常地相似，唯一的差別就在于歸并排序當(dāng)中多了遞歸調(diào)用的部分。

歸并排序是用來理解遞歸以及理解分治這個思想非常好的例子，建議新手多寫幾遍多多練習(xí)。

快速排序

快速排序同樣利用了分治的思想，我們每次做一個小的操作，讓數(shù)組的一部分變得有序，之后我們通過遞歸，將這些有序的部分組合在一起，達到整體有序。

在歸并排序當(dāng)中，我們劃分問題的方法是橫向切分，我們直接將數(shù)組一分為二，針對這兩個部分分別排序。

快排稍稍不同，它并不是針對數(shù)組的橫向切分，而是從問題本身出發(fā)的“縱向”切分。在快速排序當(dāng)中，我們解決的子問題不是對數(shù)組的一部分排序，而是提升數(shù)組的有序程度。

怎么提升呢?快排的做法非常巧妙，首先會在數(shù)組當(dāng)中尋找一個數(shù)，作為標(biāo)桿。然后，我們利用這個標(biāo)桿調(diào)整數(shù)組當(dāng)中元素的順序。將小于它的放到它的左側(cè)，大于它的放到它的右側(cè)。這么一個操作結(jié)束之后，可以肯定的是，對于我們選定的標(biāo)桿來說，它所在的位置就是排序之后它應(yīng)該在的位置。

我們來看個例子：

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

我們選擇7作為標(biāo)桿，一輪操作之后可以得到：

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

接著我們怎么做呢?很簡單，我們只需要針對標(biāo)桿前面以及標(biāo)桿后面的部分重復(fù)上述操作即可。如果還不明白的同學(xué)可以看一下下面這張動圖：

如果用C++寫過快排的同學(xué)肯定對于快排的代碼印象深刻，它是屬于典型的原理不難，但是寫起來很麻煩的算法。因為快速排序需要用到兩個下標(biāo)，寫的時候一不小心很容易寫出bug。

同樣，由于Python當(dāng)中動態(tài)數(shù)組的支持非常好，我們可以避免使用下標(biāo)來實現(xiàn)快排，這樣代碼的可讀性以及編碼難度都要降低很多。

多說無益，我們來看代碼：

def quick_sort(arr): 
    n = len(arr) 
    # 長度小于等于1說明天然有序 
    if n <= 1: 
        return arr 
   
    # pop出最后一個元素作為標(biāo)桿 
    mark = arr.pop() 
    # 用less和greater分別存儲比mark小或者大的數(shù) 
    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行，我想大家應(yīng)該都非常容易理解。

最后，我們來分析一下這兩個算法的復(fù)雜度，為什么說這兩個算法都是的算法呢?(不考慮快速排序最差情況)這個證明非常簡單，我們放一張圖大家一看就明白了：

上圖是一張遞歸樹的展開圖，無論是歸并排序還是快速排序，在遞歸當(dāng)中我們都遍歷了整個數(shù)組的元素一次，所以復(fù)雜度是。

雖然隨著遞歸層數(shù)的加深，我們把完整的數(shù)組也進行了一層層的拆分。但是橫向來看，所有拆分之后的子問題的元素之和仍然是n。所以每一層的遍歷的復(fù)雜度仍然是

，這里的n指的是總元素的個數(shù)。

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

，忽略底數(shù)的話可以寫成。

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

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

本文轉(zhuǎn)載自微信公眾號「Coder梁」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系Coder梁公眾號。