通过V8源码看一个关于JS数组排序的诡异问题
前言
前几天一个朋友在微信里面问我一个关于JS数组排序的问题。通过该问题发现了一些之前没发现的内容，下面话不多少了，来一起看看详细的介绍吧。
原始数组如下：
vardata=[
{value:4},
{value:2},
{value:undefined},
{value:undefined},
{value:1},
{value:undefined},
{value:undefined},
{value:7},
{value:undefined},
{value:4}
];
data是个数组，数组的每一项都是一个拥有value作为key的对象，值为数字或者undefined。
data .sort((x,y)=>x.value-y.value) .map(x=>x.value);
对数组的value进行排序，然后把排完序的数组进行flat处理。得到的结果如下：
[2,4,undefined,undefined,1,undefined,undefined,7,undefined,4]
显然这没有达到我们的目的。
现在我们修改一下排序，挑战一下函数的调用顺序：先对数组进行扁平化(flat)处理，然后再排序。
data .map(x=>x.value) .sort((x,y)=>x-y)
这时我们得到的结果和之前截然不同：
[1,2,4,4,7,undefined,undefined,undefined,undefined,undefined]
遇到这种情况第一感觉肯定是要去看看ECMA规范，万一是JS引擎的bug呢。
在ES6规范22.1.3.24节写道：
Callingcomparefn(a,b)alwaysreturnsthesamevaluevwhengivenaspecificpairofvaluesaandbasitstwoarguments.Furthermore,Type(v)isNumber,andvisnotNaN.Notethatthisimpliesthatexactlyoneofa
简单翻译一下就是：第二个参数comparefn返回一个数字，并且不是NaN。一个注意事项是，对于参与比较的两个数a小于b、a等于b、a大于b这三种情况必须有一个为true。
所以严格意义上来说，这段代码是有bug的，因为比较的结果出现了NaN。
在MDN文档上还有一个细节：
如果comparefn(a,b)等于0，a和b的相对位置不变。备注：ECMAScript标准并不保证这一行为，而且也不是所有浏览器都会遵守。
翻译成编程术语就是：sort排序算法是不稳定排序。
其实我们最疑惑的问题上，上面两行代码为什么会输出不同的结果。我们只能通过查看V8源码去找答案了。
V8对数组排序是这样进行的：
如果没有定义comparefn参数，则生成一个（高能预警，有坑啊）：
comparefn=function(x,y){
if(x===y)return0;
if(%_IsSmi(x)&&%_IsSmi(y)){
return%SmiLexicographicCompare(x,y);
}
x=TO_STRING(x);//<-----坑
y=TO_STRING(y);//<-----坑
if(x==y)return0;
elsereturnx
然后定义了一个插入排序算法：
functionInsertionSort(a,from,to){
for(vari=from+1;i=from;j--){
vartmp=a[j];
varorder=comparefn(tmp,element);
if(order>0){//<----注意这里
a[j+1]=tmp;
}else{
break;
}
}
a[j+1]=element;
}
为什么是插入排序？V8为了性能考虑，当数组元素个数少于10个时，使用插入排序；大于10个时使用快速排序。
后面还定义了快速排序函数和其它几个函数，我就不一一列出了。
函数都定义完成后，开始正式的排序操作：
//%RemoveArrayHolesreturns-1iffastremovalisnotsupported.
varnum_non_undefined=%RemoveArrayHoles(array,length);
if(num_non_undefined==-1){
//Therewereindexedaccessorsinthearray.
//MovearrayholesandundefinedstotheendusingaJavascriptfunction
//thatissafeinthepresenceofaccessors.
num_non_undefined=SafeRemoveArrayHoles(array);
}
中间的注释：MovearrayholesandundefinedstotheendusingaJavascriptfunction。排序之前会把数组里面的undefined移动到最后。因此第二个排序算法会把undefined移动到最后，然后对剩余的数据[4,2,1,7,4]进行排序。
而在第一种写法时，数组的每一项都是一个Object，然后最Object调用x.value-y.value进行计算，当undefined参与运算时比较的结果是NaN。
当返回NaN时V8怎么处理的呢？我前面标注过，再贴一次：
varorder=comparefn(tmp,element);
if(order>0){//<----这里
a[j+1]=tmp;
}else{
break;
}
NaN>0为false，执行了else分支代码。
思考题，以下代码的结果：
[1,23,2,3].sort()
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对毛票票的支持。