我正在尝试创建一种算法将两个有序列表合并到Python中的较大有序列表中。从本质上讲，我首先尝试隔离每个列表中的最小元素，然后比较它们以查看最小的元素，因为该数字在较大列表中也将最小。然后，我将该元素附加到空的较大列表中，然后将其从其来自原始列表中删除。然后，我尝试循环浏览原始的两个列表，从而做同一件事。在“如果”语句中，我实际上试图编程该函数，以将一个列表的其余部分附加到较大函数，如果另一个列表为空，则没有意义，因为毫无意义地询问两个列表之间的哪些元素相对较小。

Question

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

要循环浏览原始列表的副本，而不是遍历列表本身，因为在网站上搜索，我发现有时很难从循环浏览的列表中删除元素。我还试图在括号的各种配置中的“ for”语句之后保护表达式。如果有人看到问题所在的位置，那么如果您可以指出的话，或者您还有其他观察结果可以帮助我更好地构建此功能，我也非常感谢这些功能。
    

这里是一个非常简单的解决方案，仅使用非常基本的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

thins要记住：

您应该没有任何嵌套环

。 合并两个排序列表通常用于实现合并排序，合并步骤应是线性的。 即，算法应为o（n）。

Answer 1

您不应该在循环中调用

min

或

max

等。因为那将有效地引入嵌套循环，将合并变成O（n ** 2）算法，这忽略了已知列表已被分类的事实。

相似，您不应调用任何外部排序函数进行合并，因为这将导致O（n*log（n））合并（或更糟糕的是，取决于排序算法），并且再次忽略了列表已知被排序的事实。

1. 首先，（标准库）HAEPQ模块中有一个函数，可以准确地执行此操作。如果这是一个真正的问题（而不是练习），则要使用该问题。

   如果这是一个练习，有几点：
2. 您需要使用

   while循环而不是for

   循环：
3. while cab1 or cab2:

   当您的源列表中的任何一个项目中，这都会继续重复身体。
   

   您可能不应该从源列表中删除项目；这是一个相对昂贵的操作。此外，在平衡上具有
   merge_lists
函数破坏其论点将是出乎意料的。
4. 在循环中，您将参考

   cab1[i1]

   和
cab2[i2]

（在这种情况下为

Answer 2

）。

（当我键入说明时，

tomkarzes

在其他答案中键入相应的代码...）

• 这也应该工作。 它使用iter（），因此您不必跟踪两个指针。 只是一个不同的想法：

  def merge_cabs(cab1, cab2):
      cab1_iter = iter(cab1)
      cab2_iter = iter(cab2)
      """Merges two sorted iterators into a single sorted list."""
      newcab = []
      cab1_v = next(cab1_iter, None)
      cab2_v = next(cab2_iter, None)
  
      while cab1_v is not None and cab2_v is not None:
          if cab1_v <= cab2_v:
              newcab.append(cab1_v)
              cab1_v = next(cab1_iter, None)
          else:
              newcab.append(cab2_v)
              cab2_v = next(cab2_iter, None)
  
      # Append remaining elements (if any)
      if cab1_v is not None: newcab.append(cab1_v)
      newcab.extend(list(cab1_iter))
      if cab2_v is not None: newcab.append(cab2_v) 
      newcab.extend(list(cab2_iter)) 
      return newcab