python - Python QuickSort仅部分排序

我正在学习QuestRoad算法，但是出于某种原因，这个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

最佳答案

不太确定这是问题所在，但你错误地选择了pivot：

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

你总是取原始列表的头，而不是修改列表的头。
假设在某个点上你将范围缩小到左=5，右=10-你选择了列表[0]作为轴心-这不太好。
结果，在每个left>0的迭代中，忽略列表中的第一个元素，并“忽略”它-这可以解释部分排序