Python的sorted()函数使用哪种算法？

Question

Python的sorted()函数使用哪种算法？

pythonsorting

150

在Python 2.7中，Python内置的sorted函数是如何工作的？它使用什么算法？

- Hartley Brody

4

这个问题已经在这里得到回答。它使用Timsort算法进行排序。 - Aharpe

对于其他好奇的人，这篇文章非常棒：http://corte.si//posts/code/timsort/index.html - Hartley Brody

@HartleyBrody，链接已经失效了。你是指 https://corte.si/posts/code/timsort/ 还是 https://corte.si/posts/code/timsort-grayscale/ ？ - heretoinfinity

3个回答

15

这个排序算法被称为 Timsort。详见 timsort

- Pierce

13

从2.3版本开始，Python使用timsort算法。

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

- David Haynes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bgporter · Accepted Answer

Python使用一种名为Timsort的算法：

Timsort是一种混合排序算法，源自于归并排序和插入排序，旨在处理各种实际数据时表现出色。它是由Tim Peters于2002年发明，用于Python编程语言中。该算法查找已经有序的数据子集，并使用这些子集来更加有效地对数据进行排序。这是通过将已识别的子集（称为“run”）与现有的子集合并，直到满足某些条件为止来完成的。自版本2.3以来，Timsort一直是Python标准排序算法。现在它也被用于Java SE 7中的数组排序以及Android平台上的排序。