python中的快速排序和递归

Question

我尝试用Python中的两个主要函数实现快速排序：分区和快速排序。 分区函数被设计成返回两个数组——比p大和小。 在那之后，快速排序将分别对它们两个调用。 所以快速排序是这样的：

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

但根据我的理解，应该可以将分区设计为只返回一个单独的索引—划分大小数组并重新设计快速排序，如下所示：

^{pr2}$

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

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

我错过了什么？在

Answer 1

quicksort(array[:i-1])实际上并不是对数组的第一个分区调用快速排序，而是对数组第一个分区的副本调用快速排序。因此，您的代码在适当的地方对数组进行分区，然后创建两半的副本并尝试对它们进行排序（但从不对生成的数组执行任何操作），因此递归调用没有效果。在

如果您想这样做，就必须避免使用切片来复制列表，而是传递整个列表以及要应用函数的范围。在

Answer 2

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

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

（尽管您可能只是跳过了轴？）在

此外，切片是新列表，而不是视图：

^{pr2}$

这很不幸（做快速排序的典型函数程序根本不是快速排序，该死，因为它创建了一堆新数组也让我很恼火…）

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

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

Answer 3

我也有同样的问题，我的快速排序返回部分排序的列表。我发现问题是我没有在它自己的数组中返回轴。当我为pivot创建数组时，它允许递归正常工作。在

例如，我的配分函数返回而不是：

向左，向右返回

它回来了

返回左侧，pivotval，右侧