如何定义一个递归函数来合并两个排序列表并在Python中返回一个递增顺序的新列表？

I want to define a recursive function to merge two sorted lists (these two lists are sorted) and return a new list containing all the values in both argument lists with a increasing order. I know I can use list.extend() and sorted() to get that,but I don't want to use them. I just want to do some exercise about the recursion.

我想定义一个递归函数来合并两个排序列表(这两个列表被排序)并返回一个新列表,其中包含两个参数列表中具有递增顺序的所有值。我知道我可以使用list.extend()和sorted()来获取它,但我不想使用它们。我只是想对递归做一些练习。

For example:

if a = [1,2,3,4], b = [5,6,7,8]

print(function(a,b))

[1,2,3,4,5,6,7,8]

This is my code:

这是我的代码:

def combine(a:list, b:list):    
    alist = []
    if a == [] and b == []:
       return alist
    if a != [] and b == []:
       return alist + a
    if a == [] and b != []:
       return alist + b     
    if a != [] and b != []:
       if a[0] <= b[0]:
          alist.append(a[0])
          return combine(a[1:], b)
       if a[0] > b[0]:
          alist.append(b[0])
          return combine(a, b[1:])
    return alist

I always get [5,6,7,8]. How should I do to get [1,2,3,4,5,6,7,8]?

我总是[5,6,7,8]。如何获得[1,2,3,4,5,6,7,8]?

4 个解决方案

#1

Instead of return, you should add it to the alist as like below.

您应该将其添加到alist中,而不是返回,如下所示。

def combine(a, b):
    alist = []
    if a == [] and b == []:
       return alist
    if a != [] and b == []:
       return alist + a
    if a == [] and b != []:
       return alist + b
    if a != [] and b != []:
       if a[0] <= b[0]:
          alist.append(a[0])
          alist = alist +  combine(a[1:], b)
       if a[0] > b[0]:
          alist.append(b[0])
          alist = alist +  combine(a, b[1:])
    return alist

#2

Just a simpler version:

只是一个更简单的版本:

def combine(a, b):
    if a and b:
        if a[0] > b[0]:
            a, b = b, a
        return [a[0]] + combine(a[1:], b)
    return a + b

Test:

>>> combine([1,3,6,8], [2,4,5,7])
[1, 2, 3, 4, 5, 6, 7, 8]

#3

def combine(a,b):
    if not a and not b: return []
    if not a: return [b[0]] + combine(a, b[1:])
    if not b: return [a[0]] + combine(a[1:], b)
    if a[0] > b[0]:
        return [b[0]] + combine(a, b[1:])
    return [a[0]] + combine(a[1:], b)

Your test case:

你的测试用例:

In [2]: a = [1,2,3,4]

In [3]: b = [5,6,7,8]

In [4]: combine(a,b)
Out[4]: [1, 2, 3, 4, 5, 6, 7, 8]

Another test case:

另一个测试案例:

In [24]: a
Out[24]: [1, 2, 3, 8, 9]

In [25]: b
Out[25]: [1, 3, 5, 6, 7]

In [26]: combine(a,b)
Out[26]: [1, 1, 2, 3, 3, 5, 6, 7, 8, 9]

#4

Here are some alternatives:

以下是一些替代方案:

The smarter way to do this is to use merge function from the heapq module:

更智能的方法是使用heapq模块中的merge函数:

from heapq import merge
list(merge(a,b))

Test:

>>> a = [1,2,3,4,7,9]
>>> b = [5,6,7,8,12]
>>> [1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 12]

And without using recursion:

并且不使用递归:

def combine(a:list, b:list):    
    alist = []
    i,j = 0,0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            alist.append(a[i])
            i+=1
        else:
            alist.append(b[j])
            j+=1

    while i < len(a):
        alist.append(a[i])
        i+=1

    while j < len(b):
        alist.append(b[j])
        j+=1

    return alist

Test:

>>> a = [1,2,3,4,7,9]
>>> b = [5,6,7,8,12]
>>> [1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 12]