嵌套列表中的递归结果

Question

运行我的函数frisbeeSort()总是会导致列表被排序，但每个项目都在嵌套列表中。我想递归地更改原始列表而不是使用临时列表。def frisbeeSort(n):    index = n.index(min(n))    if len(n) == 1:        return n[0]    else:        n[0:index + 1] = n[index::-1]        n = [n[0], frisbeeSort(n[1:])]    return nlist1 = [12, 42, 34, 12, 76, 45, 13, 98, 234, 1]我预计[1, 12, 12, 13, 34, 42, 45, 76, 98, 234]但我不断得到[1, [12, [12, [13, [34, [42, [45, [76, [98, 234]]]]]]]]]

Answer 1

你返回一个项目，而不是一个列表len(n) == 1。您还错误地连接了两个列表。试试这个：

def frisbeeSort(n):

    index = n.index(min(n))

    if len(n) == 1:

        return [n[0]]

    else:

        n[0:index + 1] = n[index::-1]

        n = [n[0]] + frisbeeSort(n[1:])

    return n

list1 = [12, 42, 34, 12, 76, 45, 13, 98, 234, 1]

print(frisbeeSort(list1))

输出：

[1, 12, 12, 13, 34, 42, 45, 76, 98, 234]

Answer 2

我想递归地更改原始列表而不是使用临时列表

尽管接受的答案解决了“嵌套列表”问题，但我不认为它解决了上述期望。也就是说，如果你这样做：

list1 = [12, 42, 34, 12, 76, 45, 13, 98, 234, 1]

print(frisbeeSort(list1))

print(list1)

你得到：

> python3 test.py

[1, 12, 12, 13, 34, 42, 45, 76, 98, 234]

[1, 234, 98, 13, 45, 76, 12, 34, 42, 12]

>

哪里list1发生了改变，但仍未排序。这是解决使用 OP 算法对列表进行就地排序问题的一种方法：

def frisbeeSort(n, start=0):

    if start < len(n):

        index = n.index(min(n[start:]), start)

        n[start:index + 1] = n[start:index + 1][::-1]

        frisbeeSort(n, start + 1)

list1 = [12, 42, 34, 12, 76, 45, 13, 98, 234, 1]

frisbeeSort(list1)

print(list1)

输出

> python3 test.py

[1, 12, 12, 13, 34, 42, 45, 76, 98, 234]

>

您能否解释一下究竟是什么改变了原始列表而不是返回排序列表？

有两件事允许这种情况发生。首先，（默认）第二个start参数：

def frisbeeSort(n, start=0):

这允许我们保留在递归调用中排序的初始元素：

 frisbeeSort(n, start + 1)

并告诉我们从哪里开始新的最小搜索：

 index = n.index(min(n[start:]), start)

等其次，分配回数组本身：

n[start:index + 1] = n[start:index + 1][::-1]

我们正在用相同的值替换剩余的未排序元素。右边的临时数组被扔掉，原始数组被更新。

Answer 3

当您编写[n[0], frisbeeSort(n[1:])]时，它会创建一个双元素列表，其中第一个元素是n[0]，第二个元素是从frisbeeSort(n[1:])（列表）返回的值。如果您想将它们加入到一个平面列表中，您可以编写[n[0]] + frisbeeSort(n[1:]).