5

对此感到非常困惑，因为我已经为足够小的测试用例（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

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

4

3 回答 3

5

以下行中似乎有一个错字：

qsort(arr, 0, newPivotIndex)

我认为应该是这样的。

qsort(arr, left, newPivotIndex)

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

于 2012-07-28T07:13:46.063 回答
2

注意：我没有检查你的算法，所以它可能有问题/python可能出于某种原因不喜欢它，但是：快速排序将大约将排序时间从 N^2 提高到 N log(N)，但可能同样糟糕作为 N^2 取决于输入数据。使用最佳数据，N=10,000 与 N=20 相比，将慢 40,000/26 = 1538 倍。也许它只是处理？

对于最坏情况的数据，它将慢 100,000,000 / 400 = 25,000 倍。你的数据是什么？

于 2012-07-28T06:54:51.407 回答
2

Python 经常挂起深度递归函数，有时它只是终止当前会话（如果您在 IDLE 中尝试它），并开始一个新的会话而不给出任何输出。试试这个：import sys; sys.setrecursionlimit(2**30)，这可能会有所帮助，但并非总是如此。

于 2012-07-28T06:58:05.127 回答