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

攝影：產(chǎn)品經(jīng)理

廚師：kingname

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

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

在昨天的文章里面，我們已經(jīng)知道，可以使用 heapq.merge把兩個有序列表合并成新的有序列表。

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

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

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

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

再來看 [4,2]，繼續(xù)分成兩個列表 [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)。所以歸并排序在時間復雜度這個角度是優(yōu)于快速排序的。

那么如何使用代碼來實現(xiàn)呢？合并的部分請看昨天的文章，今天我們主要描述拆分的邏輯：

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

運行效果如下圖所示：

總結

以上是生活随笔為你收集整理的python归并排序理解不了_一日一技：如何更好地理解归并排序？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。