Python内置的sort()方法使用什么算法？

Question

Python内置的sort()方法使用什么算法？

pythonalgorithmsortingpython-internals

135

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

- user89862

12

当然可以查看该方法的代码 - Python 是一个开源项目。但是，该方法可能是用 C 实现的，因此您需要了解一些 C 才能理解它。 - Chris Lutz

版本重要吗？ - meder omuraliev

@melder：不是的 =）我只是想看一下专业算法:P @chris：怎么做？ - user89862

3

下载Python解释器的源代码。我不知道他们是在哪里实现sort()方法，或者解释器的格式是什么，但它一定存在于某个地方，并且我敢打赌为了速度考虑它是用C实现的。 - Chris Lutz

这里是一个使用它的例子：https://dev59.com/hnVD5IYBdhLWcg3wQZUg - Hari Ganesan

2个回答

11

在Python早期版本中，sort函数实现了一个修改版的快速排序算法。然而，在2.3版本中，为了提供默认情况下的稳定排序，它被替换成了自适应归并排序算法。stable

- Silfverstrom

2

快速排序并不被认为是“不稳定的”——按照通常使用的定义，快速排序是不稳定的——即在此排序期间，如果两个对象相等，则其原始排序顺序不会被保留。拥有不稳定的排序算法意味着您必须想出各种“魔法”来合理地对具有多个标准的数据进行排序，而不能简单地通过链接排序调用来实现——在timsort中，如果您想按DOB然后按姓名排序，则只需先按名称排序，然后再按DOB排序。您无法使用快速排序这样做。 - Tony Suffolk 66

2

@TonySuffolk66 我认为这个答案的作者可能当时正在阅读文档，并误解了“稳定”是指软件质量，而不是排序算法的属性。我编辑了答案，以便清楚地表达其含义，并添加了该概念的参考链接。 - Karl Knechtel

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

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

- Alex Martelli · Accepted Answer

好的！这里是代码，从函数islt开始，一直持续了相当长的时间;-)。正如克里斯的评论所建议的那样，这是C代码。您还需要阅读此文本文件以获取文字解释、结果等等。

如果您更喜欢阅读Java代码而不是C代码，您可以查看Joshua Bloch在Java中实现的timsort（1997年他还实现了修改后的mergesort，在Java中仍然使用，人们可以希望Java最终会转换为他最近移植的timsort）。

Java移植timsort的一些解释在这里，差异在这里（其中包含所有必需的文件指针），关键文件在这里--顺便说一句，虽然我是一个比Java程序员更好的C程序员，但在这种情况下，我发现Joshua的Java代码总体上比Tim的C代码更易读;-)。