JavaScript中数组排序sort深入理解(Array.prototype.sort)

疑问

最近在看算法书的时候看到C++中的sort方法,书中介绍是使用的快速排序。于是想起来自己天天都在写的JavaScript中的sort排序,它使用的是什么排序算法呢?各个浏览器使用的是同一种排序算法吗?

带着问题,打开了ECMA官方规范

ECMA 2015 ECMA 2016 ECMA 2017

规范中并没有写明具体使用的排序算法,只是说了JavaScript的sort方法(Array.prototype.sort)并不一定稳定!

Google Chrome浏览器

Google的Chrome浏览器的JavaScript引擎是:V8。

既然ECMA没有规定具体的排序算法,那具体实施应该是各个JavaScript引擎决定了。于是打开Chrome V8引擎的官方源码,V8引擎github源码

第239行到254行:

code:

function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.
  if (!IS_CALLABLE(comparefn)) {
    comparefn = function (x, y) {
      if (x === y) return 0;
      if (%_IsSmi(x) && %_IsSmi(y)) {
        return %SmiLexicographicCompare(x, y);
      }
      x = TO_STRING(x);
      y = TO_STRING(y);
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
}

代码中的注释明确写着:这个地方使用快速排序,但是当长度小于11的数组,使用的是插入排序。这也符合我们的正常观点,因为插入排序在数组长度小于一定值的时候是会比快速排序速度更快,快速排序在大规模数据的时候更有优势。插入排序是稳定的,快速排序是不稳定的。

知道了Chrome浏览器的排序算法。其他浏览器是不是也是这样呢?我们接着看。

Mozilla Firefox浏览器

Mozilla的Firefox浏览器的JavaScript引擎是:SpiderMonkey。

然后同样的方法,我们直接去看源码。源码地址

第2306行的注释:

code:

 /*
     * We need a temporary array of 2 * len Value to hold the array elements
     * and the scratch space for merge sort. Check that its size does not
     * overflow size_t, which would allow for indexing beyond the end of the
     * malloc'd vector.
     */

Mozilla的Firefox浏览器使用的是归并排序,归并排序是稳定的。

Safari浏览器

Safari浏览器的JavaScript引擎是:Nitro(JavaScriptCore )。

源码地址

第579行开始是这样写的:

code:

function comparatorSort(array, length, comparator){
    let valueCount = compact(array, length);
    mergeSort(array, valueCount, comparator); // 归并排序
}

function stringSort(array, length){
    let valueCount = compact(array, length);
    let strings = @newArrayWithSize(valueCount);
    for (let i = 0; i < valueCount; ++i)
        strings[i] = { string: @toString(array[i]), value: array[i] };
    bucketSort(array, 0, strings, 0); // 桶排序
}

Safari浏览器使用的是桶排序和归并排序,如果参数中含有comparator函数就使用归并排序,没有的话就使用桶排序。桶排序的稳定性不确定,归并排序是稳定的。

Microsoft Edge和IE浏览器

最后再来看看我们最难伺候的老大哥,老大哥浏览器的JavaScript引擎是:Chakra。

源码地址

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏分布式系统进阶

Kafka中的时间轮Kafka源码分析-汇总

将TimerTask对象绑定到 TimerTaskEntry上 如果这个TimerTask对象之前已经绑定到了一个 TimerTaskEntry上, 先调用t...

27910
来自专栏黑泽君的专栏

c语言基础学习11_项目实战:IDE(集成开发环境)

============================================================================= ==...

28120
来自专栏码匠的流水账

easy-rules小试牛刀

easy-rules-core-3.1.0-sources.jar!/org/jeasy/rules/api/Rule.java

38110
来自专栏WeTest质量开放平台团队的专栏

Unity3d底层数据传递分析

这篇文章主要分析了在Mono框架下,非托管堆、运行时、托管堆如何关联,以及通过哪些方式调用。内存方面,介绍了什么是封送,以及类和结构体的关系和区别。

17820
来自专栏陈仁松博客

UWP基础教程 - XAML标记扩展

标记扩展(Markup Extensions)是一个被广泛使用的XAML语言概念。通过XAML标记扩展来设定属性值,从而可以让对象元素的属性具备更加灵活和复杂的...

37370
来自专栏Golang语言社区

GO语言标准库概览

在Go语言五周系列教程的最后一部分中,我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包,提供了丰富广泛的功能特性。这里提供了概览仅仅是...

402100
来自专栏Golang语言社区

GO语言标准库概览

在Go语言五周系列教程的最后一部分中,我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包,提供了丰富广泛的功能特性。这里提供了概览仅仅是...

29640
来自专栏java学习

每日一练(2017/5/15)

Java基础 | 数据库 | Android | 学习视频 | 学习资料下载 课前导读 ●回复“每日一练”获取以前的题目! ●答案公布时间:为每期发布题目的第二...

29470
来自专栏程序员宝库

Python爬虫抓取纯静态网站及其资源

前段时间需要快速做个静态展示页面,要求是响应式和较美观。由于时间较短,自己动手写的话也有点麻烦,所以就打算上网找现成的。

37520
来自专栏Elson's web

Promise 原理探究

你真的了解Promise吗?对我而言,除了知道如何使用then解决回调地狱以外,其他的还真的一知半解。虽然ES6的generator和ES7的async awa...

72670

扫码关注云+社区

领取腾讯云代金券