递归算法中 Python 列表的可变性

Question

我编写了这个就地快速排序算法，但是修改后的数组没有传递给父调用。我是 Python 的新手，不太了解 value/reference、mutable/immutable 等的传递。任何解释指导都会很棒！

def quickSortPartition(a, l, r):
    if len(a) < 2:
        return a
    else:
        print a, l, r
        p = a[l]
        i = l + 1
        for j in range(l + 1, r+1):
            if a[j] < p:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp
                i = i + 1
        temp = a[l]
        a[l] = a[i - 1]
        a[i - 1] = temp
        firstPartition = a[:i-1]
        pivot = a[i-1]
        secondPartition = a[i:]
        if len(a[:i-1]) > 1:
            quickSortPartition(a[:i-1], 0, len(a[:i-1])-1)
        if len(a[i:]) > 1:
            quickSortPartition(a[i:], 0, len(a[i:])-1)
        return a


lines = [3, 8, 2, 5, 1, 4, 7, 6]

# print lines
quickSorted = quickSortPartition(lines, 0, len(lines)-1)

print quickSorted

Answer 1

当您使用范围为列表下标时，它会创建该列表的副本并 return 它。

因此，当您将 a[:i] 传递给您的函数时，不会考虑任何更改。

当您执行 a[i] = 3 时，它会更改您的列表。

因此，您可能想要更改代码，以便您的函数可以直接将 a 作为输入，并使用索引 i。

Answer 2

基本上，quickSortPartition returns 是一个排序列表，因此当您对 quickSortPartition 进行递归调用时，请确保捕获返回值

def quickSortPartition(a, l, r):
    if len(a) < 2:
        return a
    else:
        print a, l, r
        p = a[l]
        i = l + 1
        for j in range(l + 1, r+1):
            if a[j] < p:
                temp = a[i]
                a[i] = a[j]
                a[j] = temp
                i = i + 1
        temp = a[l]
        a[l] = a[i - 1]
        a[i - 1] = temp
        firstPartition = a[:i-1]
        pivot = a[i-1]
        secondPartition = a[i:]
        if len(a[:i-1]) > 1:
            a[:i-1] = quickSortPartition(a[:i-1], 0, len(a[:i-1])-1)
        if len(a[i:]) > 1:
            a[i:] = quickSortPartition(a[i:], 0, len(a[i:])-1)
        return a


lines = [3, 8, 2, 5, 1, 4, 7, 6]

# print lines
quickSorted = quickSortPartition(lines, 0, len(lines)-1)

print quickSorted

输出：

[3, 8, 2, 5, 1, 4, 7, 6] 0 7
[1, 2] 0 1
[5, 8, 4, 7, 6] 0 4
[8, 7, 6] 0 2
[6, 7] 0 1
[1, 2, 3, 4, 5, 6, 7, 8]

递归算法中 Python 列表的可变性

Mutability of Python list in a recursive algorithm

python

sorting

algorithm

recursion

quicksort