资讯专栏INFORMATION COLUMN

javascript排序问题探究

scola666 / 2000人阅读

摘要:通过看源代码可以发现,的数组排序算法实现的也是快速排序。而且相比较于,它就只是实现了纯粹的快速排序,完全没有中的那些性能优化的踪影。

引言

几个月前面试的时候被问过javascriptsort方法的具体算法实现,当时回答的是要看下浏览器引擎的实现,今天看到了EFE关于前端排序的博客,正好学习下

问题描述

我们经常发现不同浏览器的排序结果不同,由于不同引擎在算法选择上的差异,在浏览器中实际执行的排序效果是不一致的

Chrome中的实现

ChromeJavaScript引擎是v8。由于它是开源的,所以可以直接看源代码。

核心算法是快排,但是Chrome做了很多优化,所以看上去很复杂,Chrome做的具体优化可以看原博客,里面有比较详细的介绍,身为前端觉得基础知识不够用所以没有深入去看

Firefox中的实现

按照现有的信息,SpiderMoney内部实现了归并排序。

Microsoft Edge中的实现

Microsoft EdgeJavaScript引擎Chakra的核心部分代码已经于2016年初在Github开源。

通过看源代码可以发现,Chakra的数组排序算法实现的也是快速排序。而且相比较于v8,它就只是实现了纯粹的快速排序,完全没有v8中的那些性能优化的踪影。

解决排序稳定性的差异

从目前已知的情况来看,所有主流浏览器(包括IE6,7,8)对于数组排序算法的实现基本可以枚举:

归并排序 / Timsort

快速排序

所以,我们将快速排序经过定制改造,变成稳定排序的是不是就可以了?

一般来说,针对对象数组使用不稳定排序会影响结果。而其他类型数组本身使用稳定排序或不稳定排序的结果是相等的。

方案代码示例

"use strict";

const INDEX = Symbol("index");

function getComparer(compare) {
    return function (left, right) {
        let result = compare(left, right);

        return result === 0 ? left[INDEX] - right[INDEX] : result;
    };
}

function sort(array, compare) {
    array = array.map(
        (item, index) => {
            if (typeof item === "object") {
                item[INDEX] = index;
            }

            return item;
        }
    );

    return array.sort(getComparer(compare));
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/80320.html

相关文章

  • JavaScript专题系列20篇正式完结!

    摘要:写在前面专题系列是我写的第二个系列,第一个系列是深入系列。专题系列自月日发布第一篇文章,到月日发布最后一篇,感谢各位朋友的收藏点赞,鼓励指正。 写在前面 JavaScript 专题系列是我写的第二个系列,第一个系列是 JavaScript 深入系列。 JavaScript 专题系列共计 20 篇,主要研究日常开发中一些功能点的实现,比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里...

    sixleaves 评论0 收藏0
  • JavaScript专题之乱序

    摘要:源码地址为了简化篇幅,我们对这个数组进行分析,数组长度为,此时采用的是插入排序。插入排序的源码是其原理在于将第一个元素视为有序序列,遍历数组,将之后的元素依次插入这个构建的有序序列中。 JavaScript 专题系列第十九篇,讲解数组乱序,重点探究 Math.random() 为什么不能真正的乱序? 乱序 乱序的意思就是将数组打乱。 嗯,没有了,直接看代码吧。 Math.random ...

    I_Am 评论0 收藏0
  • JavaScript深入浅出

    摘要:理解的函数基础要搞好深入浅出原型使用原型模型,虽然这经常被当作缺点提及,但是只要善于运用,其实基于原型的继承模型比传统的类继承还要强大。中文指南基本操作指南二继续熟悉的几对方法,包括,,。商业转载请联系作者获得授权,非商业转载请注明出处。 怎样使用 this 因为本人属于伪前端,因此文中只看懂了 8 成左右,希望能够给大家带来帮助....(据说是阿里的前端妹子写的) this 的值到底...

    blair 评论0 收藏0
  • 从event loop规范探究javaScript异步及浏览器更新渲染时机

    摘要:规范中定义了浏览器何时进行渲染更新,了解它有助于性能优化。结合一些资料,对上边规范给出一些理解有误请指正每个线程都有自己的。列为,列为,列为。我们都知道是单线程,渲染计算和脚本运行共用同一线程网络请求会有其他线程,导致脚本运行会阻塞渲染。 本文转自blog 转载请注明出处 异步的思考 event loops隐藏得比较深,很多人对它很陌生。但提起异步,相信每个人都知道。异步背后的靠山就是...

    13651657101 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<