首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Node.js
Express
PPA for Ubuntu
ppa:chris-lea/node.js
宝塔
V2EX  ›  Node.js

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

  •  
  •   libook · 2018-10-30 11:28:51 +08:00 · 1725 次点击
    这是一个创建于 383 天前的主题,其中的信息可能已经有所发展或是发生改变。

    V8 Blog 原文

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

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

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

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

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

    5 回复  |  直到 2018-10-30 12:42:04 +08:00
        1
    SuperMild   2018-10-30 11:47:59 +08:00
    据说 Python 里的 TimSort 算法实现得非常优秀(当时来说)。
        2
    neoblackcap   2018-10-30 11:53:08 +08:00
    @SuperMild 因为 Python 里面的 TimSort 是 TimSort 算法作者写的,他写完之后才有 TimSort
        3
    SuperMild   2018-10-30 11:59:11 +08:00
    @neoblackcap 真心牛逼
        4
    hahastudio   2018-10-30 12:00:49 +08:00
    It was implemented by Tim Peters in 2002 for use in the Python programming language.
        5
    jjx   2018-10-30 12:42:04 +08:00
    流畅的 Python 中有写
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2041 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 00:34 · PVG 08:34 · LAX 16:34 · JFK 19:34
    ♥ Do have faith in what you're doing.