如何在不使用“sort”函数的情况下使用递归对列表进行排序？

Question

我需要在不使用“sort”函数的情况下使用递归对列表进行排序

def gensort(L):
    """ sorts all numbers in the List from lowest to highest
    L is a list
    return value is the sorted list
    """
    if len(L) == 0:
        return goodlist
    else:
        goodlist = []
        goodlist.append(min(L))
        L.remove(min(L))
        return gensort(L)
gensort([7, 9, 4, 3, 0, 5, 2, 6, 1, 8]) 

我想创建第二个列表并使用append和remove来填充它，但这是因为递归的本质；该列表在每次递归时都会被占用

Answer 1

您正在为gensort（）的每次调用创建一个列表。不要只获取一个参数，而是获取两个参数（原始列表和新列表）。然后使用空列表作为默认值，如下所示：

def gensort(L, goodlist=[]):
    """ sorts all numbers in the List from lowest to highest
    L is a list
    return value is the sorted list
    """
    if len(L) == 0:
       return goodlist
    else:
       goodlist.append(min(L))
       L.remove(min(L))
       return gensort(L, goodlist)

   print(gensort([7, 9, 4, 3, 0, 5, 2, 6, 1, 8]) )

这样，您可以在每次递归调用时保留列表

Answer 2

您不需要跟踪两个列表。以下工作很好：

def gensort(L):
    if len(L) == 1:
        return L
    sorted_list = [min(L)]
    L.remove(min(L))
    return sorted_list + gensort(L)

下面是正在发生的事情：

gensort([4, 1, 3, 2]) # returns [1] + gensort([4, 3, 2])
gensort([4, 3, 2]) # returns [2] + gensort([4, 3])
gensort([4, 3]) # returns [3] + gensort([4])
gensort([4]) # returns [4]

在返回值中替换，可以得到：

[1] + [2] + [3] + [4]

其计算结果为[1, 2, 3, 4]