亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python對兩個有序列表進(jìn)行合并和排序的例子

系統(tǒng) 1837 0

假設(shè)有2個有序列表l1、l2,如何效率比較高的將2個list合并并保持有序狀態(tài),這里默認(rèn)排序是正序。

思路是比較簡單的,無非是依次比較l1和l2頭部第一個元素,將比較小的放在一個新的列表中,以此類推,直到所有的元素都被放到新的列表中。

考慮2個列表l1 = [2], l2 = [1],如何將他們合并呢?(注意:下面實現(xiàn)會改變l1和l2本來的值)

復(fù)制代碼 代碼如下:

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)用只處理一個元素,通過遞歸來解決問題。
復(fù)制代碼 代碼如下:

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有一個為空的時候就終止,可以稍微改寫一下:
復(fù)制代碼 代碼如下:

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)來做,再稍微改寫一下:
復(fù)制代碼 代碼如下:

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ī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产欧美乱码在线看 | 亚洲香蕉久久一区二区 | 日本高清免费不卡在线播放 | 嫩草社区 | 欧美一级免费片 | 黄色成人在线播放 | 欧美成人xxxx | 欧美高清国产 | 91精品推荐 | 另类婷婷 | 狠狠色丁香婷婷综合激情 | 久久精品国产曰本波多野结衣 | 欧美白人猛性xxxxx交69 | 综合视频在线 | 亚洲一区中文字幕在线观看 | 香蕉久久综合精品首页 | 色婷婷一区二区三区四区成人 | 国产亚洲综合一区二区在线 | 天天久久综合 | 久热在线视频精品网站 | 国产自产拍精品视频免费看 | 91精品久久国产青草 | 成年女人色毛片免费 | 天天操网| 插插射射| 久久这里只有精品免费播放 | 福利入口在线观看 | 在线观看一区二区精品视频 | 欧美四虎影院 | 天天爽天天碰狠狠添 | 久久噜噜噜 | 99精品视频看国产啪视频 | 国产欧美日韩精品高清二区综合区 | 色一情| 91福利在线看| 精品区| 日韩视频一区 | 国产欧美日韩综合二区三区 | 久久国产毛片 | 麻豆国产原创最新在线视频 | 五月久久亚洲七七综合中文网 |