Python QuickSort 最大递归深度

Question

(Python 2.7.8 Windows)

我正在对不同的排序算法(快速、冒泡和插入)进行比较，大多数情况下都按预期进行，快速排序对于长列表来说要快得多，而冒泡和插入对于非常短的列表和已经排序的列表来说更快.

引起问题的是快速排序和前面提到的“已排序”列表。我什至可以对 100000 个项目的列表进行排序而不会出现问题，但是对于从 0...n 开始的整数列表，限制似乎要低得多。 0...500 有效，但即使是 0...1000 也会给出:

RuntimeError: maximum recursion depth exceeded in cmp

快速排序:

def quickSort(myList):
    if myList == []:
        return []
    else:
        pivot = myList[0]
        lesser = quickSort([x for x in myList[1:] if x < pivot])
        greater = quickSort([x for x in myList[1:] if x >= pivot])
        myList = lesser + [pivot] + greater
        return myList

是代码有问题，还是我遗漏了什么？

Answer 1

有两件事正在发生。

首先，Python 有意将递归限制在固定深度。与 Scheme 不同，Scheme 会一直为递归调用分配帧，直到内存用完，Python(至少是最流行的实现，CPython)只会分配 sys.getrecursionlimit()。失败前的帧数(默认为 1000)。这是有原因的，*但实际上，这与这里无关；您只需要知道它会这样做这一事实。

其次，正如您可能已经知道的那样，虽然 QuickSort 是 O(N log N) most 列表，但它的最坏情况是 O(N ^2)——特别是(使用标准数据透视规则)已经排序的列表。当发生这种情况时，您的堆栈深度可能最终为 O(N)。因此，如果您有 1000 个元素，按最坏情况顺序排列，并且您已经进入堆栈的一帧，您就会溢出。

您可以通过以下几种方式解决此问题:

• 将代码重写为可迭代的，具有显式堆栈，因此您仅受堆内存而非堆栈深度的限制。
• 确保始终首先递归到较短的一侧，而不是左侧。这意味着即使在 O(N^2) 的情况下，您的堆栈深度仍然是 O(log N)。但前提是您已经完成了上一步。**
• 使用随机、三中位数或其他使常见情况不同于已排序的最坏情况的主元规则。 (当然，有人仍然可以故意对您的代码进行 DoS；使用快速排序确实无法避免这种情况。)Wikipedia article对此进行了一些讨论，并链接到经典的 Sedgewick 和 Knuth 论文。
• 使用具有无限堆栈的 Python 实现。***
• sys.setrecursionlimit(max(sys.getrecursionlimit(), len(myList)+CONSTANT))。这样，如果您不能腾出足够的空间，您将立即失败，原因很明显，否则通常不会失败。 (但是你可能——你可能已经在堆栈的 900 步深处开始排序了……)但这是个坏主意。****。而且，你还得想出正确的CONSTANT，一般情况下是不可能的。*****

---

_{* 从历史上看，CPython 解释器递归调用自身以进行递归 Python 函数调用。而C栈的大小是固定的；如果你超出了结尾，你可能会出现段错误，堆满整个堆内存，或者其他各种问题。这可以改变——事实上，Stackless Python有了这个改变，一开始基本上只是 CPython。但核心开发人员有意选择不这样做，部分原因是他们不想鼓励人们编写深度递归代码。}

_{** 或者，如果您的语言会自动消除尾调用，但 Python 不会那样做。但是，正如 gnibbler 指出的那样，您可以编写一个混合解决方案——在小端递归，然后在大端手动展开尾递归——不需要显式堆栈。}

_{*** Stackless 和 PyPy 都可以这样配置。}

_{**** 一方面，最终你会让 C 堆栈崩溃。}

_{***** 常量并不是真正的常量；这取决于你已经在堆栈中有多深(可通过将 sys._getframe() 走到顶部来不可移植地计算)以及比较函数需要多少松弛度等(不可计算根本没有，你只需要猜测)。}