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

不entirley肯定这是问题，但你错艇员选拔支点：

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

您始终以原始列表的头部，而不是修改列表的头部。

假设您在某一时刻将范围缩小到了左= 5，右= 10 - 您选择了列表[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 

枢轴索引只应在交换时增加。作为if声明的一部分，将i = i + 1缩进与交换深度相同。

奖金问题：你为什么分区两次？

Answer 3

也最后交换;

A [左]，A [I - 1] = A [I-1]，A [左] #swap

应该与枢轴完成。

除此之外，Quicksort在原地工作。所以你不需要下面的回报;

返回列表[：透视] + [列表[透视] +列表[支点+ 1：]

Answer 4

不完全的回答你的问题，但我相信它仍然是最相关的。

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

在算法中，选择最左边的项目会使算法在数组已经排序或接近排序的最差情况下运行。

枢轴的选择应该随机执行以避免此问题。

检查算法在*上执行问题：http://en.wikipedia.org/wiki/Quicksort#Implementation_issues

其实，检查孔的文章。这值得你花时间。