我看了谈话“三个美丽的快速排序”，并开始忙于快速排序。我在python中的实现与c非常相似（选择数据透视图，围绕它的分区并在越来越大的分区上递归）。我以为不是
pythonic 。

所以这是在python中使用列表理解的实现。

def qsort(list):
    if list == []: 
        return []
    pivot = list[0]
    l = qsort([x for x in list[1:] if x < pivot])
    u = qsort([x for x in list[1:] if x >= pivot])
    return l + [pivot] + u

让我们将递归称为qsortR。现在我注意到对于大型列表，qsortR的运行速度比qsort慢得多。实际上，对于递归方法，即使对于1000个元素，“最大递归深度都超过了cmp”。我在sys.setrecursionlimit中重置了它。

一些数字：

list-compr 1000 elems 0.491770029068
recursion 1000 elems 2.24620914459
list-compr 2000 elems 0.992327928543
recursion 2000 elems 7.72630095482

所有代码都在这里。

我有一些问题：

• 为什么列表理解如此之快？
• 对python递归限制的一些启示。在某些情况下，我首先将其设置为100000？
  • （“优化尾递归”到底是什么意思，如何完成？）
• 尝试对1000000个元素进行排序占用了我的笔记本电脑的内存（使用递归方法）。如果我想对这么多元素排序，该怎么办？什么样的优化是可能的？