python - python中的快速排序和递归

Question

我正在尝试使用 2 个主要函数(分区和快速排序)在 Python 中实现快速排序。分区函数的设计使其返回 2 个数组 - 比 p 大和小。在分别调用它们两个之后快速排序。所以快速排序是这样工作的:

def quicksort(array)
    pivot = 0 # pivot choice is irrelevant
    left,right = partition(array,pivot)
    quicksort(left)
    quicksoft(right)
    return left+right

但根据我的理解，应该可以将分区设计为仅返回一个索引 - 分隔更大和更小的数组并重新设计快速排序如下:

def quicksort(array)
    pivot = 0 # pivot choice is irrelevant
    i = partition(array,pivot)
    quicksort(array[:i-1])
    quicksoft(array[i:])
    return array

但是这个实现返回部分排序的数组

original array [5, 4, 2, 1, 6, 7, 3, 8, 9]
sorted array [3, 4, 2, 1, 5, 7, 6, 8, 9]

我在这里错过了什么？

Answer 1

如果没有看到您的代码，很难确定，但一个可能的错误是 i-1:

>>> [1,2,3,4][:2]
[1, 2]
>>> [1,2,3,4][2:]
[3, 4]

(尽管您可能只是跳过了枢轴？)

此外，切片是新列表，而不是 View :

>>> l = [1,2,3,4]
>>> l[2:][0] = 'three'
>>> l
[1, 2, 3, 4]

这很不幸(执行快速排序的典型函数式程序根本不是快速排序，该死的，因为它正在创建一堆新数组，这也让我很烦......)

您可以通过传递整个列表加上 lo/hi 索引来解决第二个问题:

def quicksort(data, lo=0, hi=None):
    if hi is None: hi = len(data)
    ....