一日一技：如何更好地理解歸併排序？

• 2019 年 10 月 7 日
• 筆記

攝影：產品經理

廚師：kingname

請確保你已經看了我昨天的公眾號文章。昨天的內容是今天的基礎。

一日一技：在 Python 裡面如何合併多個有序列表並使得結果依然有序？

在昨天的文章裡面，我們已經知道，可以使用 heapq.merge把兩個有序列表合併成新的有序列表。

現在，我們來設計一個排序演算法，對列表：[1,4,2,0,4,5,1,-3,-8,188,34] 進行排序。

我們現在先把列表拆分成a列表：[1,4,2,0,4,5]和b列表 [1,-3,-8,188,34]。如果我們能夠分別讓這兩個列表各自有序，然後應用昨天的方法，合併一下，最終結果自然就出來了。

那麼如何讓這兩個列表各自有序呢？我們以 [1,4,2,0,4,5]為例。繼續把它拆分為兩個列表 [1,4,2]和 [0,4,5]。只要這兩個列表各自有序，那麼合併一下就行了。

我們再來看 [1,4,2]，如何讓它有序呢？我們繼續分成兩個列表 [1]和 [4,2]。顯然只有一個元素的列表 [1]是有序的。

再來看 [4,2]，繼續分成兩個列表 [4]和 [2]。這兩個列表都只有一個元素，所以他們都是有序的。此時對他們進行合併，得到 [2,4]。

[1] 與 [2,4]合併，得到 [1,2,4]。

[1,2,4]與 [0,4,5]合併，得到 [0,1,2,4,4,5]。

[0,1,2,4,4,5]與 [-8,-3,1,34,188]合併，得到 [-8,-3,0,1,1,2,4,4,5,34,188]。

排序完成。

整個過程先拆分再合併，這種排序演算法叫做 歸併演算法。它的時間複雜度始終是 O(nlogn)。而我們常常聽說的快速排序，只有在最好的情況下時間複雜度才能達到 O(nlogn)。所以歸併排序在時間複雜度這個角度是優於快速排序的。

那麼如何使用程式碼來實現呢？合併的部分請看昨天的文章，今天我們主要描述拆分的邏輯：

import heapq    def sort(target):      if not target:          return []      if len(target) == 1:          return target      left = target[:len(target) // 2]      right = target[len(target)//2 :]      sorted_left = sort(left)      sorted_right = sort(right)      result = heapq.merge(sorted_left, sorted_right)      return result

運行效果如下圖所示：

未聞Code

PYTHON乾貨日更