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]

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

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

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