常用浏览器排序源码解析

常见问题

很多人在使用sort时,肯定这样写过:

[1, 2, 5, 40].sort()
>> [1, 2, 40, 5]

显然结果是不符合期望的,为什么会这样呢,我们先来看下ECMAScript标准。

ECMAScript标准

sort方法的参数

可选参数: compareFunction

形式:function (a, b) {

​ // need return number

​ }

未传入compareFunction时

1 将需要比较的值转换为字符串;

2 按照UTF-16编码,升序排序。

已传入compareFunction时

compareFunction(a, b) {

​ return < 0 // a排在b前面

​ return === 0 // a和b此次不交换位置

​ return > 0 // b在a前面

}

空元素处理

undefined、empty、null元素都移到数组最后,且不参与比较。

根据ECMAScript标准的定义,不传入compareFunction时,数组元素被当作字符串进行排序了,所以会出现不符合期望的结果。

浏览器实现

Firefox - SpiderMonkey

主流程

spider_1.png

1 ToBoject:

​ 调用C++方法,将数组转换成Object;

2 ArrayNativeSort(C++)排序;

3 如果2失败,使用js的排序方法排序。

ArrayNativeSort(C++)

spider_2.png

1 MergeSort:

​ 使用自底向上的归并排序;

​ 对于length <= 3的小数组,使用插入排序;

2 MoveHoles:

​ 将数组中的空元素移动到数组末尾。

js实现的排序

spider_3.png

MergeSort:

​ length < 24,使用插入排序;

​ length >= 24,使用自底向上的归并排序,初始sz = 4,使用插入排序初始化,使数组局部有序。

Chrome - v8

主流程

v8_1.png

1 TO_OBJECT:

​ 调用C++方法,将数组转换成Object;

​ 移动空元素至数组末尾;

2 如果未传入compareFunction,将compareFunction置为C++的SmiLexicographicCompare方法;

3 排序。

排序

v8_2.png

length <= 10,插入排序;

length > 10,快速排序和插入排序的混合排序。

Safari - JavaScriptCore

主流程

core_1.png

1 toObject:

​ 将数组转换成Object;

2 compact:

​ 移动空元素至数组末尾;

3 排序

排序

bucketSort(未传入compareFunction):
core_2.png

​ 桶排序,使每个桶大小 < 32;

​ 每个桶中使用归并排序。

mergeSort(已传入compareFunction):
core_3.png

​ 自底向上的归并排序

应用

数字数组排序

使用sort给数字数组排序时,注意必须传入compareFunction

稳定的排序

有时,我们希望数组中重复元素排序前后的相对位置不发生变化,我们就需要使用稳定的排序,例如插入、归并排序;

但是,ECMAScript标准并未规定浏览器是否需要实现稳定的排序,这时,我们需要借助第三方库或者自己实现排序。

评论

暂无评论