V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
libook
V2EX  ›  Node.js

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

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

    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
    SuperMild
        1
    SuperMild  
       2018-10-30 11:47:59 +08:00
    据说 Python 里的 TimSort 算法实现得非常优秀(当时来说)。
    neoblackcap
        2
    neoblackcap  
       2018-10-30 11:53:08 +08:00
    @SuperMild 因为 Python 里面的 TimSort 是 TimSort 算法作者写的,他写完之后才有 TimSort
    SuperMild
        3
    SuperMild  
       2018-10-30 11:59:11 +08:00
    @neoblackcap 真心牛逼
    hahastudio
        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.
    jjx
        5
    jjx  
       2018-10-30 12:42:04 +08:00
    流畅的 Python 中有写
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5351 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 09:03 · PVG 17:03 · LAX 02:03 · JFK 05:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.