Python程序中的快速排序对于更大的输入大小挂起？

Question

对此我感到很困惑，因为我已经为足够小的测试用例（N=20）验证了正确的逻辑输出。我试着做N=10000个数字，程序就挂了，我不明白为什么。。。我已经尽可能简单地实现了这个算法。在

另外，在我的N=10k列表上调用sorted(data)似乎可以立即工作。所以我确信我的算法在某个地方卡住了。在

代码如下：

def QuickSort(array):
    qsort(array, 0, len(array))


def qsort(arr, left, right):
    if ((right - left) < 2):
        return

    pivotIndex = choosePivot0(arr, left, right)

    newPivotIndex = partition(arr, pivotIndex, left, right)

    qsort(arr, 0, newPivotIndex)
    qsort(arr, newPivotIndex + 1, right)

def partition(arr, pivotIndex, left, right):
    swap(arr, pivotIndex, left)
    pivot = arr[left]
    i = left + 1
    for j in range(left+1, right):
        if (arr[j] < pivot):
            swap(arr, i, j)
            i = i + 1

    swap(arr, left, i-1) #put pivot back where it belongs
    #cobj.count = cobj.count + (right - left - 1) #add m-1 the #of comparisons
    return (i-1) #give back where the pivot resides



def swap(array, i, j):
    temp = array[i]
    array[i] = array[j]
    array[j] = temp

def choosePivot0(array, left, right):
    return randint(left, right-1) #random

所以我很困惑为什么会发生这种事。谢谢你的帮助。在

Answer 1

下面一行似乎有一个错误：

qsort(arr, 0, newPivotIndex)

我想应该是这样的。在

^{pr2}$

否则，该函数将以某种方式只对某些输入数据集起作用。这就是为什么算法会卡住。在

Answer 2

注意：我没有检查您的算法，因此可能有问题/python可能出于某些原因不喜欢它，但是： 快速排序大约可以将排序时间从N^2提高到N log（N），但可能与N^2一样糟糕，具体取决于输入数据。对于最优数据，N=10000比N=20慢40000/26=1538倍。也许只是处理？在

最坏情况下的数据是100000000/400=25000倍。你的数据是什么？在

Answer 3

Python经常挂起执行深层递归函数，有时它只是终止当前会话（如果您是在空闲状态下尝试的话），然后启动一个新的会话，而根本不给出任何输出。试试这个：import sys; sys.setrecursionlimit(2**30)，这可能会有所帮助，但并不总是这样。在