假設有2個有序列表l1、l2，如何效率比較高的將2個list合并并保持有序狀態(tài)，這里默認排序是正序。
思路是比較簡單的，無非是依次比較l1和l2頭部第一個元素，將比較小的放在一個新的列表中，以此類推，直到所有的元素都被放到新的列表中。
考慮2個列表l1 = [2], l2 = [1]，如何將他們合并呢？(注意：下面實現(xiàn)會改變l1和l2本來的值)
復制代碼
代碼如下:
def signle_merge_sort(l1, l2):
??? tmp = []
??? if l1[0] < l2[0]:
??????? tmp.append(l1[0])
??????? tmp.extend(l2)
??????? del l2[0]
??? else:
??????? tmp.append(l2[0])
??????? tmp.extend(l1)
??????? del l1[0]
??? return tmp
這真的只能處理一個元素的情形，還不能解決問題，不過好歹我們有一個大概的思路了。如果有列表中2個元素，上面的方法就不行了。我們需要解決邊界判斷問題，即當l1或者l2有一個為空的時，將剩下的一個list加到排序結(jié)果的尾部。然后確保函數(shù)每次調(diào)用只處理一個元素，通過遞歸來解決問題。
復制代碼
代碼如下:
def recursion_merge_sort1(l1, l2):
??? tmp = []
??? if len(l1) == 0:
??????? tmp.extend(l2)
??????? return tmp
??? elif len(l2) == 0:
??????? tmp.extend(l1)
??????? return tmp
??? else:
??????? if l1[0] < l2[0]:
??????????? tmp.append(l1[0])
??????????? del l1[0]
??????? else:
??????????? tmp.append(l2[0])
??????????? del l2[0]
??????? tmp += recursion_merge_sort1(l1, l2)
??? return tmp
上面的程序有2個問題：if判斷太多；每次都要初始化tmp，對內(nèi)存使用似乎不太友好。考慮到程序在l1或者l2有一個為空的時候就終止，可以稍微改寫一下：
復制代碼
代碼如下:
def _recursion_merge_sort2(l1, l2, tmp):
??? if len(l1) == 0 or len(l2) == 0:
??????? tmp.extend(l1)
??????? tmp.extend(l2)
??????? return tmp
??? else:
??????? if l1[0] < l2[0]:
??????????? tmp.append(l1[0])
??????????? del l1[0]
??????? else:
??????????? tmp.append(l2[0])
??????????? del l2[0]
??????? return _recursion_merge_sort2(l1, l2, tmp)
def recursion_merge_sort2(l1, l2):
??? return _recursion_merge_sort2(l1, l2, [])
但是對于Python而言，即使是尾遞歸，效率也不是那么高，為了避免爆棧，通常還是會用循環(huán)來做，再稍微改寫一下:
復制代碼
代碼如下:
def loop_merge_sort(l1, l2):
??? tmp = []
??? while len(l1) > 0 and len(l2) > 0:
??????? if l1[0] < l2[0]:
??????????? tmp.append(l1[0])
??????????? del l1[0]
??????? else:
??????????? tmp.append(l2[0])
??????????? del l2[0]
??? tmp.extend(l1)
??? tmp.extend(l2)
??? return tmp
今天栽了個坑，好好反省，就是這樣。
更多文章、技術(shù)交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
