我看了三个漂亮的快速排序的演讲，正在玩快速排序。我在python中的实现与c非常相似（选择pivot，围绕它的分区以及在越来越小的分区上递归）。我认为这不是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。现在我注意到对于大（r）列表，qsortR的运行速度比qsort慢得多。实际上，即使对于递归方法的1000个elems，“最大递归深度也超过了cmp”。我在sys. setpostsionlimited中重置了它。
一些数字：
list-compr 1000 elems 0.491770029068
recursion 1000 elems 2.24620914459
list-compr 2000 elems 0.992327928543
recursion 2000 elems 7.72630095482
所有代码都在这里。
我有几个问题：
>
为什么列表理解速度这么快？
因为列表理解意味着C循环，它比使用Python的for块的慢得多。
关于python中递归限制的一些启示。我先设置为100000什么情况下要小心？
以防内存溢出。
尝试对1000000个元素进行排序占用了我笔记本电脑的内存（使用递归方法）。如果我想对这么多元素进行排序，我该怎么办？可以进行什么样的优化？
Python的递归会产生这样的开销，因为每个函数调用都会为每个调用分配大量的堆栈内存空间。
一般来说，迭代是答案（在统计上99%的用例中将提供更好的性能）。
谈到内存结构，如果您有简单的数据结构，如字符、整数、浮点数：使用内置的数组，它比列表的内存效率高得多。
您是否尝试过编写分区的非递归实现？我怀疑性能差异纯粹是分区实现。您正在为实现中的每个元素递归。
更新
这是一个快速实现。它仍然不是超级快甚至高效的，但它比你原来的递归方法好得多。
>>> def partition(data):
... pivot = data[0]
... less, equal, greater = [], [], []
... for elm in data:
... if elm < pivot:
... less.append(elm)
... elif elm > pivot:
... greater.append(elm)
... else:
... equal.append(elm)
... return less, equal, greater
...
>>> def qsort2(data):
... if data:
... less, equal, greater = partition(data)
... return qsort2(less) + equal + qsort2(greater)
... return data
...
我还认为，在“传统”版本中生成的临时列表数量更多。
当内存变得非常大时，尝试将列表理解与就地算法进行比较。下面的代码在对100K整数进行排序时执行时间接近，但是在对1M整数进行排序时，您可能会被困在列表理解解决方案中。我已经使用4Gb机器进行了测试。完整代码：http://snipt.org/Aaaje2
class QSort:
def __init__(self, lst):
self.lst = lst
def sorted(self):
self.qsort_swap(0, len(self.lst))
return self.lst
def qsort_swap(self, begin, end):
if (end - begin) > 1:
pivot = self.lst[begin]
l = begin + 1
r = end
while l < r:
if self.lst[l] <= pivot:
l += 1
else:
r -= 1
self.lst[l], self.lst[r] = self.lst[r], self.lst[l]
l -= 1
self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]
# print begin, end, self.lst
self.qsort_swap(begin, l)
self.qsort_swap(r, end)
