关于Python内置的sort()方法

Question

sort()Python使用的内置方法是什么算法？是否可以查看该方法的代码？

Answer 1

当然!代码在这里,从函数开始islt并继续QUITE一段时间;-).正如克里斯的评论所暗示的那样,它是C代码.您还需要阅读此文本文件以获取文本说明,结果等.

如果您更喜欢阅读Java代码而不是C代码,那么您可以查看Joshua Bloch在Java和Java中的timsort实现(Joshua也是1997年实现了仍在Java中使用的修改后的mergesort的人,可以希望Java将会最终切换到他最近的timsort端口).

关于timsort的Java端口的一些解释在这里,diff就在这里(指向所有需要的文件),密钥文件在这里 --FWIW,而我是一个比Java程序员更好的C程序员,在这种情况下我发现Joshua的Java代码比Tim的C代码更具可读性;-).

@Chris,"浏览Python源代码"是我所有浏览器书签栏的快捷方式 - 它指向http://svn.python.org/view/python/trunk/ ;-). (4认同)
`listsort.txt`的[当前版本](http://hg.python.org/cpython/file/default/Objects/listsort.txt)添加了一些解决常见混淆的注释. (3认同)
执行对列表项的赋值(就像list_ass_slice执行对列表切片的赋值),与排序无关.我想"赋值"的缩写使这个名字变得有趣...... (2认同)
@Alex:从那以后,大多数存储库转移到了Mercury:http://hg.python.org/ (2认同)

Answer 2

我只想提供一个非常有用的链接,我错过了Alex的全面答案:Python的timsort的高级解释(带有图形可视化!).

(是的,算法现在基本上称为Timsort)

Answer 3

在早期的python版本中,sort函数实现了quicksort的修改版本.然而,它被认为是不稳定的,并且从2.3开始他们转而使用自适应合并算法.

快速排序不是“被认为不稳定”——根据常用的定义，快速排序是不稳定的——也就是说，如果两个对象在排序过程中相等，则不会保留它们的原始顺序。拥有不稳定的排序算法意味着您必须想出各种“魔法”来合理地使用多个条件对数据进行排序，而不是简单地能够链接排序调用 - 如果您想按 DOB 然后按名称排序，请在 timsort 中，您只需先按名称排序，然后按 DOB 排序即可，但使用快速排序无法做到这一点 (2认同)
@TonySuffolk66我认为这个答案的作者当时可能一直在阅读文档并误解“稳定”是指软件质量 - 而不是排序算法的属性。我编辑了答案，以便清楚地表达其含义，并添加了该概念的参考链接。 (2认同)