V8 7.0 数组开始使用 TimSort 排序算法

2018-10-30 11:28:51 +08:00
 libook

V8 Blog 原文

博客中说他们以前使用的快速排序算法在性能上并不稳定，相同长度的数组在理想情况和最差情况下的排序性能相差较大，于是改用 TimSort 算法。

这个算法是非常有名的一个算法，在保证高性能的同时还能保证性能稳定。

TimSort 的设计思路很新颖（当然也可能借鉴了其他算法）：既然单个算法会遇到最好情况和最差情况导致性能不稳定，那么是不是可以先分析数组特征，然后扬长避短在多种算法中选取合适的算法进行排序呢？

所以实际上 TimSort 是多种排序算法+分块算法+翻转，是一种“混合排序算法调度算法”。

有很多语言引擎默认使用 TimSort 作为原生排序算法，如 Python （ 2.3 开始）、Java SE 7、Android platform、GNU Octave。

4012 次点击
所在节点    Node.js
5 条回复
SuperMild
2018-10-30 11:47:59 +08:00
据说 Python 里的 TimSort 算法实现得非常优秀（当时来说）。
neoblackcap
2018-10-30 11:53:08 +08:00
@SuperMild 因为 Python 里面的 TimSort 是 TimSort 算法作者写的，他写完之后才有 TimSort
SuperMild
2018-10-30 11:59:11 +08:00
@neoblackcap 真心牛逼
hahastudio
2018-10-30 12:00:49 +08:00
It was implemented by Tim Peters in 2002 for use in the Python programming language.
jjx
2018-10-30 12:42:04 +08:00
流畅的 Python 中有写

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/502479

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX