V8 7.0数组开始使用TimSort排序算法
发布于 1 年前 作者 libook 1181 次浏览 来自 分享

V8 Blog 原文

博客中说他们以前使用的快速排序算法在性能上并不稳定,相同长度的数组在理想情况和最差情况下的排序性能相差较大,于是改用TimSort算法。 这个算法是非常有名的一个算法,在保证高性能的同时还能保证性能稳定。 TimSort的设计思路很新颖(当然也可能借鉴了其他算法):既然单个算法会遇到最好情况和最差情况导致性能不稳定,那么是不是可以先分析数组特征,然后扬长避短在多种算法中选取合适的算法进行排序呢? 所以实际上TimSort是多种排序算法+分块算法+翻转,是一种“混合排序算法调度算法”。 有很多语言引擎默认使用TimSort作为原生排序算法,如Python(2.3开始)、Java SE 7、Android platform、GNU Octave。

回到顶部