Python快速排序仅部分排序

Question

我正在学习快速排序算法，但由于某种原因，这个python实现的输出只是部分排序的，对于较大的输入，我得到了"达到的最大递归深度"。在过去的几天里，我一直在思考这个问题，我知道这可能真的很愚蠢，但我似乎不明白，所以我很感激任何帮助。

def ChoosePivot(list):
    return list[0]  
def Partition(A,left,right):
    p = ChoosePivot(A)
    i = left + 1
    for j in range(left + 1,right + 1): #upto right + 1 because of range()
        if A[j] < p:
                A[j], A[i] = A[i], A[j] #swap
                i = i + 1
    A[left], A[i - 1] = A[i-1], A[left] #swap
    return i - 1
def QuickSort(list,left, right):
    if len(list) == 1: return   
    if left < right:
        pivot = Partition(list,left,right)              
        QuickSort(list,left, pivot - 1)
        QuickSort(list,pivot + 1, right)
        return list[:pivot] + [list[pivot]] + list[pivot+1:]
sample_array = [39,2,41,95,44,8,7,6,9,10,34,56,75,100] 
print "Unsorted list: " 
print sample_array
sample_array = QuickSort(sample_array,0,len(sample_array)-1)
print "Sorted list:"
print sample_array

Answer 1

不能完全确定这是问题所在，但您错误地选择了枢轴：

def ChoosePivot(list):
    return list[0]  
def Partition(A,left,right):
    p = ChoosePivot(A)
    ....

你总是拿着原始列表的头，而不是修改后的列表的头。

假设在某个时刻，你将范围缩小到左=5，右=10——你选择了list[0]作为轴心——这不太好。
因此，在left>0的每次迭代中，您都会忽略列表中的第一个元素，并"错过"它——这可以解释部分排序

Answer 2

def ChoosePivot(list):
    return list[0]

正如阿米特所说，这是错误的。您需要p = A[left]。然而，还有另一个问题：

if A[j] < p:
    A[j], A[i] = A[i], A[j] #swap
i = i + 1

数据透视索引只应在交换时递增。将i = i + 1缩进到与交换相同的深度，作为if语句的一部分。

额外的问题：为什么要分区两次？

Answer 3

也是最后一次交换；

A[i-left]，A[i-1]=A[i-1]，A[left]#交换

应该使用pivot完成。

除此之外，Quicksort在原地工作。所以你不需要跟随返回；

return list[：pivot]+[list[pivot]]+list[ppivot+1:]

Answer 4

这并不是你问题的答案，但我相信它仍然是最相关的。

在实现快速排序时，选择始终位于同一位置的枢轴是算法的一个缺陷。可以生成一个数字序列，使您的算法在O（n^2）时间内运行，并且绝对运行时间可能比bubblesort更差。

在算法中，选择最左边的项会使算法在数组已经排序或即将排序的最坏情况下运行。

应随机选择枢轴以避免出现此问题

查看维基百科中的算法实现问题：http://en.wikipedia.org/wiki/Quicksort#Implementation_issues

实际上，检查一下孔的文章。这值得你花时间。