为什么我在Python中的快速排序函数不起作用

Question

这是我的代码：

def quicksort(arr):
if len(arr) > 1:
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < arr[0]:
left.append(arr[i])
else:
right.append(arr[i])
quicksort(left)
quicksort(right)
arr = left + [arr[0]] + right

它以前是有效的，但我试图通过不返回arr而是在函数中更改它来简化代码。现在它已经不起作用了。为什么？

Answer 1

当您运行这行代码时：

arr = left + [arr[0]] + right

您正在将名称arr重新绑定到本地值，与原始参数的连接将丢失。

Answer 2

这是一个作用域问题。在Python中，一旦使用赋值"="运算符，就会认为您不再希望与所讨论的原始对象有任何关系。

假设arr在进入函数时最初有一个361(简化(的引用。现在，如果您更改了对象的单个元素，它在内存中的引用仍然是361，因此该元素将在原始对象中更改。但是，您的行arr = left + [arr[0]] + right现在创建了局部变量arr，该变量在函数内部有一个引用，比如366。现在，对该变量所做的任何更改都不会转移到原始arr，参考361。

由于不再返回此变量，因此无法对原始对象进行任何更改。

Answer 3

arr = left + [arr[0]] + right

此行在本地作用域中创建一个新列表arr。这就是为什么外部arr没有被修改的原因。

你需要找到一种方法，使arr不会被重新申报或再次反弹，这里有一个例子：

def quicksort(arr):
if len(arr) > 1:
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < arr[0]:
left.append(arr[i])
else:
right.append(arr[i])
quicksort(left)
quicksort(right)
right = [arr[0]] + right
arr.clear()
arr.extend(*[left + right])