将两个已排序的列表合并为一个更大的排序列表

Question

我正在尝试创建一个合并函数,将在我正在进行的合并排序中使用.

我遇到了一些麻烦,我似乎无法找到错误.

我评论它试图向你们展示我的思考过程:

def merge(aList, bList):
    newList = []
    while (len(aList) > 0) & (len(bList) > 0):  #Loop until both lists are empty
        if aList[0] < bList[0]:         #If the first item of aList is smaller than the first item of bList
            newList.append(aList[0])    #add that item to the new list
            aList.pop(0)                #and remove it from the original list

        else:                           #If it gets here, that means the first item of bList was smaller
            newList.append(bList[0])    #So put the first item of bList is the new list
            bList.pop(0)                #and remove it from the original
    return newList

list1 = [3, 4, 8, 9]
list2 = [1, 2, 5, 8]

print(merge(list1, list2))
print(list1)
print(list2)

输出:

[1, 2, 3, 4, 5, 8]
[8, 9]
[0]

我期待list1和list2为空,但由于某种原因,list1中似乎有一个未放置的8和9.有人有想法吗？

Answer 1

这是一个使用Python库heapq的版本:

import heapq

def merge(aList, bList)
    return list(heapq.merge(aList, bList))

Answer 2

即使列表中没有元素，也要确保不断添加元素。您当前的代码一旦aList或bList为空就会停止，这可能不是您想要的。

False您可以通过使用表达式来评估空列表这一事实来做到这一点if：

def merge(aList, bList):
    newList = []
    while (aList or bList): # single empty list won't stop the loop
        if not bList or (aList and aList[0] < bList[0]):
            # either bList is empty, or aList has next item
            newList.append(aList.pop(0))
        else:
            # bList has next item
            newList.append(bList.pop(0))
    reutrn newList

list1 = [3, 4, 8, 9]
list2 = [1, 2, 5, 8]

print(merge(list1, list2))
print(list1)
print(list2)

输出：

sh-4.2# python3 main.py                                                                              
[1, 2, 3, 4, 5, 8, 8, 9]                                                                             
[]                                                                                                   
[]