Python中两个排序列表的合并排序算法forloop构造困难

Question

我试图在Python中创建一个算法，将两个有序列表合并成一个更大的有序列表。从本质上讲，我首先尝试分离每个列表中的最小元素，然后比较它们，看哪个最小，因为在较大的列表中，这个数字也是最小的。然后，我将该元素附加到空的较大列表中，然后将其从原始列表中删除。然后，我试着在原来的两个列表中循环做同样的事情。在“if”语句中，我基本上尝试对函数进行编程，以便在另一个列表为空/变为空时将一个列表的其余部分附加到较大的函数中，因为没有必要询问两个列表之间的哪些元素相对较小

def merge_cabs(cab1, cab2):
    for (i <= all(j) for j in cab1):
        for (k <= all(l) for l in cab2):
            if cab1 == []:
                newcab.append(cab2)
            if cab2 == []:
                newcab.append(cab1)
            else:
                    k = min(min(cab1), min(cab2))
                    newcab.append(k)
                    if min(cab1) < min(cab2):
                        cab1.remove(min(cab1))
                    if min(cab2) < min(cab1):
                        cab2.remove(min(cab2))
    print(newcab)


cab1 = [1,2,5,6,8,9]
cab2 = [3,4,7,10,11]
newcab = []
merge_cabs(cab1, cab2)

不幸的是，我在构建for循环时遇到了一些麻烦。我试图分离最小值的一种方法是，正如我在两行“for”中所写的那样。现在，Python返回“SyntaxError:invalid syntax”，指向第一行“for”中的冒号。我尝试构建for循环的另一种方法是：

def merge_cabs(cabs1, cabs2):
    for min(i) in cab1:
        for min(j) in cab2:

我还尝试将表达式全部写在一行中，如下所示：

def merge_cabs(cab1, cab2):
    for min(i) in cabs1 and min(j) in cabs2:

并且循环浏览原始列表的副本，而不是循环浏览列表本身，因为在网站中搜索时，我发现有时很难从循环浏览的列表中删除元素。我还尝试在各种括号配置中保护“for”语句后面的表达式。如果有人看到了问题所在，如果你能指出它，或者如果你有任何其他的观察结果可以帮助我更好地构造这个函数，我也会非常感激

Answer 1

首先，（标准库）heapq模块中有一个函数，用于执行此操作，heapq.merge；如果这是一个真正的问题（而不是一个练习），您希望使用该问题

如果这是一个练习，有两点：

• 您需要使用while循环而不是for循环：

  while cab1 or cab2:
  

  当任何一个源列表中有任何项时，这将继续重复正文

• 您可能不应该从源列表中删除项目；这是一个相对昂贵的操作。此外，总的来说，让一个merge_lists函数销毁它的参数是出乎意料的

  在循环中，您将引用cab1[i1]和cab2[i2]（在条件中，引用i1 < len(cab1)）

（当我输入解释时，Tom Karzes在another answer中输入了相应的代码…）

Answer 2

下面是一个非常简单的解决方案，它只使用非常基本的Python操作：

def merge_cabs(cab1, cab2):
    len1 = len(cab1)
    len2 = len(cab2)

    i = 0
    j = 0
    newcab = []

    while i < len1 and j < len2:
        v1 = cab1[i]
        v2 = cab2[j]
        if v1 <= v2:
            newcab.append(v1)
            i += 1
        else:
            newcab.append(v2)
            j += 1

    while i < len1:
        newcab.append(cab1[i])
        i += 1

    while j < len2:
        newcab.append(cab2[j])
        j += 1

    return newcab

要记住的事情：

1. 您应该没有任何嵌套循环。合并两个排序列表通常用于实现合并排序，合并步骤应为线性。也就是说，算法应该是O（n）

2. 您需要同时遍历两个列表，在east step中选择最小值，然后只推进包含最小值的列表。当其中一个列表被使用时，未使用列表中的其余元素只是按顺序追加

3. 您不应该在循环中调用min或max等，因为这将有效地引入一个嵌套循环，将合并变成一个O（n**2）算法，该算法忽略了已知列表已排序的事实

4. 类似地，您不应该调用任何外部排序函数来进行合并，因为这将导致O（n*log（n））合并（或者更糟，取决于排序算法），并且再次忽略已知列表已排序的事实