Python内置sort()方法使用什么算法？
Python里面的sort()方法用的是什么算法呢？我们能不能看看这个方法的代码呢？
3 个回答
2
从Python 3.11版本开始，sort()这个排序功能使用了一种叫做powersort的排序算法。这种算法是合并排序的一种，它能够利用数据中已经排好序的部分，也就是我们说的“运行”（runs）。当要排序的长度小于64时，Python会切换到一种叫做二分插入排序的算法。
关于Python的具体实现细节，可以查看这里：https://github.com/python/cpython/blob/main/Objects/listsort.txt
12
在早期的Python版本中，sort函数使用了一种改进版的快速排序算法。不过在2.3版本中，这个算法被换成了一种自适应的归并排序算法，这样默认情况下就能提供一种稳定的排序方式。
147
当然可以！这段代码的链接在这里，从函数islt开始，后面还有很多内容;-)。正如Chris的评论所说，这段代码是用C语言写的。你还可以查看这个文本文件，里面有文字说明、结果等等。
如果你更喜欢看Java代码而不是C代码，可以看看Joshua Bloch为Java实现的timsort（Joshua还是1997年实现了现在Java中使用的改进版归并排序的人，希望Java最终能切换到他最近的timsort版本）。
关于Java版timsort的一些解释在这里，差异对比在这里（里面有所有需要文件的指向），关键文件在这里 -- 顺便说一下，虽然我在C语言编程上比在Java编程上更有经验，但在这种情况下，我觉得Joshua的Java代码整体上比Tim的C代码更易读;-）。