问题:关于Python的内置sort()方法

sort()Python 的内置方法使用什么算法?可以看看该方法的代码吗?

What algorithm is the built in sort() method in Python using? Is it possible to have a look at the code for that method?


回答 0

当然!代码在这里,从函数开始,islt进行相当一段时间;-)。就像克里斯的评论所暗示的那样,它是C代码。您还需要阅读此文本文件,以获得文本说明,结果等。

如果您喜欢阅读Java代码而不是C代码,则可以看看Joshua Bloch在Java中和Java中实现timsort(Joshua也是在1997年实现了仍在Java中使用的经过修改的mergesort的人,并且人们希望Java将最终改用他最近的timsort港口)。

timsort的Java端口的一些说明在这里,diff在这里(带有指向所有需要的文件的指针),关键文件在这里 -FWIW,尽管我是比Java程序员更好的C程序员,在这种情况下,我发现Joshua的Java代码比Tim的C代码更具可读性;-)。

Sure! The code’s here, starting with function islt and proceeding for QUITE a while;-). As Chris’s comment suggests, it’s C code. You’ll also want to read this text file for a textual explanation, results, etc etc.

If you prefer reading Java code than C code, you could look at Joshua Bloch’s implementation of timsort in and for Java (Joshua’s also the guy who implemented, in 1997, the modified mergesort that’s still used in Java, and one can hope that Java will eventually switch to his recent port of timsort).

Some explanation of the Java port of timsort is here, the diff is here (with pointers to all needed files), the key file is here — FWIW, while I’m a better C programmer than Java programmer, in this case I find Joshua’s Java code more readable overall than Tim’s C code;-).


回答 1

我只是想提供一个非常有用的链接,而我在Alex的其他全面答案中却没有找到它:对Python timsort的高级解释(带有图形可视化!)。

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

I just wanted to supply a very helpful link that I missed in Alex’s otherwise comprehensive answer: A high-level explanation of Python’s timsort (with graph visualizations!).

(Yes, the algorithm is basically known as Timsort now)


回答 2

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

In early python-versions, the sort function implemented a modified version of quicksort. However, it was deemed unstable and as of 2.3 they switched to using an adaptive mergesort algorithm.


声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。