0

我正在学习快速排序算法，但由于某种原因，这个 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
4

4 回答 4

2

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

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

你总是占据原始列表的头部，而不是修改后的列表的头部。

假设在某个时候您将范围缩小到 left=5,right=10 - 您选择 list[0] 作为枢轴 - 这不好。
结果，在left>0您忽略列表中的第一个元素并“错过”它的每次迭代中 - 这可以解释部分排序

于 2012-04-06T06:55:13.497 回答
1 
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

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

于 2012-04-06T07:14:05.657 回答
0

也是最后一次交换；

A[左], A[i - 1] = A[i-1], A[左] #swap

应该用枢轴完成。

除此之外，快速排序就地工作。所以你不需要以下回报；

返回列表[:pivot] + [list[pivot]] + list[pivot+1:]

于 2012-04-06T10:35:58.123 回答
-1

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

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

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

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

检查 Wikipedia 中算法的实施问题：http ://en.wikipedia.org/wiki/Quicksort#Implementation_issues

实际上，检查洞文章。值得你花时间。

于 2012-08-24T12:25:48.703 回答