Python：函数参数范围

Question

我正在学习 QuickSort，我练习使用 Python 来完成它。但是出乎我意料的事情发生了。看来我的 QuickSort 函数只排序一次。为什么？

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


def quick_sort(array):
    if len(array) <= 1:
        # print(array)
        # print('')
        return
    else:
        # print(array)
        # print('')
        pivot = array[0]
        i = 1
        j = len(array) - 1
        while i != j:
            while array[j] >= pivot and i < j:
                j -= 1
            while array[i] <= pivot and i < j:
                i += 1
            if i < j:
                array[i], array[j] = array[j], array[i]
                # print(array)
                # print('')
        if array[0] > array[i]:
            array[0], array[i] = array[i], array[0]
        # print(array)
        # print('')
        array_left = array[0:i]
        array_right = array[i + 1:]
        quick_sort(array_left)
        quick_sort(array_right)


def test_quick_sort():

    # print(array)
    quick_sort(array)
    print(array)


test_quick_sort()

输出为[2, 1, 0, 3, 6, 7, 5, 4, 8, 9]。
如果你取消所有的#，你可以看到每一步的输出都是绝对正确的。

Answer 1

在 python 中，当您对列表进行切片时，会创建一个包含值的新列表。

list1 = [1, 2, 3, 4, 5]
list2 = list1[:3] #[1, 2, 3]
list2[0] = 5 #[5, 2, 3]

print(list1, list2) #[1, 2, 3, 4, 5] [5, 2, 3]

对切片列表所做的任何更改都不会反映在原始列表中。

在您的 quick_sort 函数中，您将列表分成左右两部分，并对它们调用了 quick_sort。这不影响原始列表的顺序。

要解决此问题，请修改您的函数，改为接收一个列表以及排序位置的开始和结束索引。

def quick_sort(array, start, end):
    if end - start <= 1:
        return
    else:
        pivot = array[start]
        i = start + 1
        j = end - 1
        while i != j:
            while array[j] >= pivot and i < j:
                j -= 1
            while array[i] <= pivot and i < j:
                i += 1
            if i < j:
                array[i], array[j] = array[j], array[i]
        if array[start] > array[i]:
            array[start], array[i] = array[i], array[start]
        quick_sort(array, start, i)
        quick_sort(array, i, end)

Python：函数参数范围

Python: Scope of function parameters

python

recursion

quicksort