python的sorted()使用什么算法？

Question

python的sorted()使用什么算法？

Har*_*ody 67 python sorting

可能重复:
关于python的内置sort()方法

名字说明了一切.

我试图向某人解释为什么他们应该使用Python的内置sorted()函数而不是自己滚动,我意识到我不知道它使用什么算法.

如果重要,我们正在谈论python 2.7

Answer 1

bgp*_*ter 122

Python使用名为Timsort的算法:

Timsort是一种混合排序算法,源自合并排序和插入排序,旨在很好地处理各种真实数据.它是由Tim Peters在2002年发明的,用于Python编程语言.该算法查找已经排序的数据的子集,并使用子集更有效地对数据进行排序.这是通过将已识别的子集(称为运行)与现有运行合并直到满足某些标准来完成的.从版本2.3开始,Timsort一直是Python的标准排序算法.它现在也用于在Java SE 7和Android平台上对数组进行排序.

它不仅使用了非常聪明的算法,而且还在手动优化的C中实现它.即使您通过将伪代码转换为Python来实现它,它也会慢一个数量级,并且需要更多的内存. (18认同)
这是一个非常令人印象深刻的算法:OP的朋友非常难以自己开发更好的东西. (8认同)
@bgporter确切地说,这个bug不是在Timsort中,而是在它的参考实现中.根据[维基百科文章](https://en.wikipedia.org/wiki/Timsort#Formal_verification),它已经修复. (4认同)
一篇有趣的论文说它在TimSort中发现了一个错误(并提供了修复):http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-如何做修复,它/ (2认同)

Answer 2

Dav*_*nes 9

从 2.3 Python 开始使用 timsort。

更多信息：http : //bugs.python.org/file4451/timsort.txt

Answer 3

小智 6

排序算法称为Timsort.见timsort

归档时间：	13 年，3 月前
查看次数：	63692 次
最近记录：	13 年，3 月前