快速排序RecursionError

Question

我编写了一个关于快速排序的代码，问题是，我得到了一个递归错误的大型数组，例如，超过1000个值。但是，我没有小数组的问题。我不知道为什么我会犯错。有人能帮我吗？

我的守则：

last = object()
def quicksort(array, start= 0, ende = last):

    if ende is last:
        ende = (len(array) -1)


    def partition(array, anfang, ende):
        piv_index = anfang
        piv = array[piv_index]

        while anfang < ende:
            while anfang < len(array) and array[anfang] <= piv:
                anfang += 1

            while array[ende] > piv:
                ende -= 1

            if anfang < ende:
                array[anfang], array[ende] = array[ende], array[anfang]

        array[ende], array[piv_index] = array[piv_index], array[ende]

        return ende

    if start < ende:

        p = partition(array, start, ende)

        quicksort(array, start, p-1)
        quicksort(array, p+1, ende)
    return(array)

Answer 1

正如Barmar在注释中提到的，Python中有一个递归限制，似乎是1000。

您可以使用函数getrecursionlimit()看到系统上的实际值，该函数在我的系统上是1000 (Python3)。

如果需要使用getrecursionlimit(imit)，可以将递归限制设置得更高。

您说在使用1000个数字进行测试时遇到了递归错误。您必须测试一个严格的降序列表，例如1000, 999, 998, ..., 1，这将达到极限。

实际上，将递归限制设置为1000。

和包含999项的输入列表

以及你对枢轴的选择

你会达到极限的。

有998个号码你会没事的。

如果您知道数组的最大大小，则选择更高的递归限制可能是有意义的。否则，您必须考虑一个可能的递归错误。

除了选择另一种合适的排序算法之外，您还能做些什么：

如果possible

• choose是随机/因此(这里有几个选项)

• 重写快速排序程序，以便迭代(对一些人来说比较困难，但不需要递归深度问题)，则
• 设置递归限制以满足您的需要。

当然，这些选择各有优缺点，所以你必须做出妥协(正如我经常听到的那样，你必须死在死亡之一)。

Answer 2

为了避免堆栈溢出，可以将堆栈空间限制为O(log2(n))，方法是在较小的分区上递归，对于较大的分区循环。最坏的情况下，时间复杂度仍然是O(n^2)。该代码也是Hoare分区方案的一个变体，需要进行一些清理。示例代码，它使用中间元素作为枢轴，并包含在快速排序函数中的分区逻辑。

def qsort(a, lo, hi):           # hoare, post inc, dec
    while(lo < hi):
        p = a[(lo + hi) // 2]   # pivot
        i = lo
        j = hi
        while(i <= j):
            while(a[i] < p):
                i += 1
            while(a[j] > p):
                j -= 1
            if(i > j):
                break
            a[i],a[j] = a[j],a[i]
            i += 1
            j -= 1
        # recurse on smaller part, loop on larger part
        if((j - lo) <= (hi - i)):
            qsort(a, lo, j)
            lo = i
        else:
            qsort(a, i, hi)
            hi = j