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

2019-11-25 18:22:28

字體：大中小

供稿：網(wǎng)友

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

思路是比較簡(jiǎn)單的，無(wú)非是依次比較l1和l2頭部第一個(gè)元素，將比較小的放在一個(gè)新的列表中，以此類推，直到所有的元素都被放到新的列表中。

考慮2個(gè)列表l1 = [2], l2 = [1]，如何將他們合并呢？(注意：下面實(shí)現(xiàn)會(huì)改變l1和l2本來(lái)的值)

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

這真的只能處理一個(gè)元素的情形，還不能解決問題，不過好歹我們有一個(gè)大概的思路了。如果有列表中2個(gè)元素，上面的方法就不行了。我們需要解決邊界判斷問題，即當(dāng)l1或者l2有一個(gè)為空的時(shí)，將剩下的一個(gè)list加到排序結(jié)果的尾部。然后確保函數(shù)每次調(diào)用只處理一個(gè)元素，通過遞歸來(lái)解決問題。

復(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個(gè)問題：if判斷太多；每次都要初始化tmp，對(duì)內(nèi)存使用似乎不太友好。考慮到程序在l1或者l2有一個(gè)為空的時(shí)候就終止，可以稍微改寫一下：

復(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, [])

但是對(duì)于Python而言，即使是尾遞歸，效率也不是那么高，為了避免爆棧，通常還是會(huì)用循環(huán)來(lái)做，再稍微改寫一下:

復(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

今天栽了個(gè)坑，好好反省，就是這樣。

上一篇：Python程序設(shè)計(jì)入門(1)基本語(yǔ)法簡(jiǎn)介

下一篇：用Python輸出一個(gè)楊輝三角的例子