Python QuickSort最大递归深度
Python QuickSort最大递归深度
提问于 2014-11-24 23:40:00
(Python2.7.8 Windows)
我正在对不同的排序算法(快速排序算法、气泡排序算法和插入算法)进行比较，大多数情况下，快速排序算法与长列表相比要快得多，对于非常短的列表和排序过高的排序算法，插入速度更快。
引起问题的是快速排序和前面提到的“已排序”列表。我甚至可以对100000项进行排序，没有问题，但是对于0.n中的整数列表，限制似乎要低得多。0.500工作，但甚至.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代码有问题吗，还是我漏掉了什么？
回答 2
Stack Overflow用户
发布于 2014-11-24 23:52:26
您选择每个子列表的第一项作为支点。如果列表已经有序，这意味着您的greater子列表是除第一项之外的所有项，而不是其中的一半。本质上，每个递归调用只能处理一个项。这意味着您需要进行的递归调用的深度将与完整列表中的项目数大致相同。当您点击大约1000项时，Python的内置限制就会溢出。您将遇到类似的问题，排序列表已经处于相反的顺序。
要纠正这一点，请使用文献中提出的解决办法之一，例如随机选择一个项目作为第一、第二和最后项目的中心或中位数。
Stack Overflow用户
发布于 2014-11-24 23:48:36
始终选择第一个(或最后一个)元素作为枢轴，对于一些常见输入的快速排序(最坏的情况)性能会有问题，正如您已经看到的。
一种比较有效的方法是选择第一、中、后三种元素的平均值。
您不希望使枢轴选择过于复杂，否则它将主导搜索的运行时。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27116255
复制相关文章
相似问题
腾讯云开发者
