python - 将整数添加到排序列表 - 递归

Question

我需要递归地将 int 添加到列表中，稍后还添加其他功能。

def insert_in_list(x, tree):
    if not tree:
        return tree
    elif isinstance(tree[0], list):
        return inserting(x, tree[0]) + inserting(x, tree[1:])
    elif x < tree[0]:
        tree.insert(0, x)
        return tree
    else:
        return inserting(x, tree[1:])

我正在使用insert()。但由于某种原因，我的列表似乎仅限于 3 个值。例如

>>> insert_in_list(2, [1,5,10]) 
[2,5,10]

1 发生了什么？

Answer 1

因为你的最后一个案例丢弃了第一个值。您将首先调用 insert_in_list(x, tree) 并最终出现情况 4，其中它将调用 insert_in_list(x, [5, 10])。然后，这将在情况 3 中结束，并在第一个位置插入 x，然后返回新列表 [2, 5, 10]。

处理索引可能更容易:

def insert_in_list(x, tree, index=0):
    if not tree:
        return tree
    elif x < tree[index]:
        tree.insert(index, x)
        return tree
    else:
        return insert_in_list(x, tree, index+1)

我刚刚省略了第二种情况，因为它与您的问题无关:

>>> insert_in_list(2, [1,5,10])
[1, 2, 5, 10]

请注意，如果您的树已排序，您还可以进行二分而不是递归来查找应插入值的位置。例如，使用递归二分并基于 bisect.insort_right :

def insert_in_list(x, tree, lo=0, hi=None):
    if not tree:
        return tree

    if hi is None:
        hi = len(tree)
    if lo < hi:
        mid = (lo + hi) // 2
        if x < tree[mid]: 
            hi = mid
        else: 
            lo = mid + 1
        return insert_in_list(x, tree, lo, hi)

    tree.insert(lo, x)
    return tree