假設(shè)有2個有序列表l1、l2,如何效率比較高的將2個list合并并保持有序狀態(tài),這里默認(rèn)排序是正序。
思路是比較簡單的,無非是依次比較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個元素,上面的方法就不行了。我們需要解決邊界判斷問題,即當(dāng)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ù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
