python-3.x - 在切片上使用递归进行错误的冒泡排序；列表最终没有排序

Question

def bubble_sort(l):
    if len(l) == 1:
      return
    for i in range(len(l) - 1):
        if l[i] > l[i + 1]:
            l[i], l[i + 1 ] = l[i + 1], l[i]
    bubble_sort(l[:-1])

l = [3, 2, 1]
bubble_sort(l)
print(l)

给出

[2,1,3]

我正在尝试通过递归冒泡排序对列表进行升序排序。结果列表不是排序的列表。如果发现缩进错误，请忽略。

Answer 1

您的代码的问题在于，在 python 中，切片运算符返回切片的新副本，而不是引用。也就是如果我们进行如下操作

lst = [1, 2, 3, 4]
slice = lst[2:]
slice[0] = -5
print(lst)

输出将是 [1, 2, 3, 4]。原来的名单不会改变。这是您代码中的问题；当您将列表的一部分传递给递归函数时，您不会对原始列表进行排序。解决此问题的一种方法是传递索引而不是切片。可能的解决方案如下:

from random import shuffle


def bubble_sort(lst, n):
    if n == 1:
        return
    for i in range(n - 1):
        if lst[i] > lst[i+1]:
            lst[i], lst[i+1] = lst[i+1], lst[i]
    bubble_sort(lst, n - 1)


n = 50
x = [i for i in range(50)]
shuffle(x)
bubble_sort(x, n)
print(x)

我们将要排序的子列表的索引传递给我们的递归函数，并且总是在没有任何切片的情况下对原始列表进行操作。上面的代码应该按预期输出排序列表。