博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
javascript排序问题探究
阅读量:5757 次
发布时间:2019-06-18

本文共 1124 字,大约阅读时间需要 3 分钟。

引言

几个月前面试的时候被问过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));}

转载地址:http://tgvkx.baihongyu.com/

你可能感兴趣的文章
《老梁四大名著情商课》笔记- 刚上班,别做林黛玉,也别做孙悟空
查看>>
一个前端入门后需要看看的
查看>>
Springboot如何优雅的解决ajax+自定义headers的跨域请求[转]
查看>>
《口算大作战 2》标准版
查看>>
实验0 了解和熟悉操作系统
查看>>
Canvas rontate(旋转) 使用误区
查看>>
使用C#调用金诚信71x系列读卡器的DLL
查看>>
EL有11个隐含对象
查看>>
后缀自己主动机(SAM)学习指南
查看>>
关于iOS Tabbar的一些设置
查看>>
Filter介绍,运行顺序,实例
查看>>
如何在页面上减少用户操作?
查看>>
RGB颜色矩提取算法——Matlab
查看>>
爬取豆瓣电影TOP250
查看>>
selenium2之文件上传
查看>>
多线程大串讲之二: 多线程同步的学习[1]
查看>>
导出mysql数据时,socket目录
查看>>
linux学习笔记1:无操作系统时LED驱动
查看>>
LeetCode-46-Permutations
查看>>
美团测试开发面经
查看>>