演算法淺談——分治演算法與歸併、快速排序

2020 年 3 月 5 日
筆記

點擊上方藍字，和我一起學技術。

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

我們可以認為在遞歸的過程當中，我們通過函數自己調用自己，將大問題轉化成了小問題，因此簡化了編碼以及建模。今天這篇文章呢，就正式和大家聊一聊將大問題簡化成小問題的分治演算法的經典使用場景——排序。

排序演算法

排序演算法有很多，很多博文都有總結，號稱有十大經典的排序演算法。我們信手拈來就可以說上來很多，比如插入排序、選擇排序、桶排序、希爾排序、快速排序、歸併排序等等。老實講這麼多排序演算法，但我們實際工作中並不會用到那麼多，凡是高級語言都有自帶的排序工具，我們直接調用就好。

為了應付面試以及提升自己演算法能力呢，用到的也就那麼幾種。今天我們來介紹一下利用分治思想實現的兩種經典排序演算法——歸併排序與快速排序。

歸併排序

我們先來講歸併排序，歸併排序的思路其實很簡單，說白了只有一句話：兩個有序數組歸併的複雜度是O(n)。

我們舉個例子：

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數組為止，我們可以很方便地寫出以上操作的程式碼：

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數組永遠不會越界，如此就可以簡化很多程式碼了（前提，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]

通過上面的這個過程我們可以發現，在歸併排序的時候，我們先一直往下遞歸切分數組，直到所有的切片當中只有一個元素天然有序。接著一層一層地歸併回來，當所有元素歸併結束的時候，數組就完成了排序。這也就是歸併排序的全部過程。

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

最後，我們來試著用程式碼來實現。之前我曾經在面試的時候被要求在白板上寫過歸併排序，當時我用的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

你看，無論是思想還是程式碼實現，歸併排序並不難，就算一開始不熟悉，寫個兩遍也一定沒問題了。

理解了歸併排序之後，再來學快速排序就不難了，我們一起來看快速排序的演算法原理。

快速排序

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

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

快排稍稍不同，它並不是針對數組的橫向切分，而是從問題本身出發的」縱向「切分。在快速排序當中，我們解決的子問題不是對數組的一部分排序，而是提升數組的有序程度。

怎麼提升呢？我們在數組當中尋找一個數，作為標杆，我們利用這個標杆調整數組當中元素的順序。將小於它的放到它的左側，大於它的放到它的右側。這麼一個操作結束之後，可以肯定的是，這個標杆所在的位置就是排序完成之後，它應該在的位置。

我們來看個例子：

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行，我想大家應該都非常容易理解。

最後，我們來分析一下這兩個演算法的複雜度，為什麼說這兩個演算法都是