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

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

  •  
  •   libook · 355 天前 · 1674 次点击
    这是一个创建于 355 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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   354 天前
    据说 Python 里的 TimSort 算法实现得非常优秀(当时来说)。
        2
    neoblackcap   354 天前
    @SuperMild 因为 Python 里面的 TimSort 是 TimSort 算法作者写的,他写完之后才有 TimSort
        3
    SuperMild   354 天前
    @neoblackcap 真心牛逼
        4
    hahastudio   354 天前
    It was implemented by Tim Peters in 2002 for use in the Python programming language.
        5
    jjx   354 天前
    流畅的 Python 中有写
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2169 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 21ms · UTC 03:37 · PVG 11:37 · LAX 20:37 · JFK 23:37
    ♥ Do have faith in what you're doing.