常用浏览器排序源码解析
文章目录
常见问题
很多人在使用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
主流程

1 ToBoject:
调用C++方法,将数组转换成Object;
2 ArrayNativeSort(C++)排序;
3 如果2失败,使用js的排序方法排序。
ArrayNativeSort(C++)

1 MergeSort:
使用自底向上的归并排序;
对于length <= 3的小数组,使用插入排序;
2 MoveHoles:
将数组中的空元素移动到数组末尾。
js实现的排序

MergeSort:
length < 24,使用插入排序;
length >= 24,使用自底向上的归并排序,初始sz = 4,使用插入排序初始化,使数组局部有序。
Chrome - v8
主流程

1 TO_OBJECT:
调用C++方法,将数组转换成Object;
移动空元素至数组末尾;
2 如果未传入compareFunction,将compareFunction置为C++的SmiLexicographicCompare方法;
3 排序。
排序

length <= 10,插入排序;
length > 10,快速排序和插入排序的混合排序。
Safari - JavaScriptCore
主流程

1 toObject:
将数组转换成Object;
2 compact:
移动空元素至数组末尾;
3 排序
排序
bucketSort(未传入compareFunction):
桶排序,使每个桶大小 < 32;
每个桶中使用归并排序。
mergeSort(已传入compareFunction):
自底向上的归并排序
应用
数字数组排序
使用sort给数字数组排序时,注意必须传入compareFunction
稳定的排序
有时,我们希望数组中重复元素排序前后的相对位置不发生变化,我们就需要使用稳定的排序,例如插入、归并排序;
但是,ECMAScript标准并未规定浏览器是否需要实现稳定的排序,这时,我们需要借助第三方库或者自己实现排序。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论