Python中的QuickSort - 程序挂起以适应更大的输入尺寸？

Question

对此非常困惑,因为我已经为足够小的测试用例验证了正确的逻辑输出(N = 20).我尝试N = 10,000个数字,程序只是挂起,我不明白为什么......我已经尽可能简单地实现了算法.

此外,呼叫sorted(data)我的N = 10k列表似乎几乎立即工作.所以我确信我的算法只会卡在某处.

这是代码:

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)

我认为它应该是这样的.

qsort(arr, left, newPivotIndex)

否则该函数将以某种方式仅对某些输入数据集起作用.这就是算法卡住的原因.