JavaScript Array.sort() 运行与V8源码运行有差异?

WingDust
  • 67

在对 Array.sort() 进行深入研究时

发现sort()方法在运行时的插入排序算法(长度<=22时使用这个算法)有差异。


先来看V8源码的运行

V8源码第710行:

var InsertionSort = function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
        var order = comparefn(tmp, element);
        if (order > 0) {
          a[j + 1] = tmp;
        } else {
          break;
        }
      }
      a[j + 1] = element;
    }
  };

于是我写了测试代码来检测

测试代码:

var a = [77,33,44,55,66] 
var InsertionSort = function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      for (var j = i - 1; j >= from; j--) {
        var tmp = a[j];
        var order = comparefn(tmp, element);
        if (order > 0) {
          a[j + 1] = tmp;
        } else {
          break;
        }
      }
      a[j + 1] = element;
    }
  };
function comparefn(a,b){
    if(a<b)return -1;
    if (a>b)return 1;
return 0;
}
InsertionSort(a,0,5)
console.log(a)

测试中compartfn它的比较顺序为

次数ab备注
17733[33,77,44,55,66]
27744[33,77,44,55,66]
33344[33,44,77,55,66]
47755[33,44,77,55,66]
54455[33,44,55,77,66]
67766[33,44,55,77,66]
75566[33,44,55,66,77]

而在实际使用Array.sort()中却不是这上顺序
Array.sort()代码检测:

let c = [77,33,44,66,55]
c.sort((a,b)=>{
if (a<b){ console.log(c); return -1;}
if (a>b){ console.log(c); return 1;}
return 0;
})

比较顺序为

次数ab备注
13377
24433
34477
44433
56644
66677
75566
85544

这个是实现上有差异吗?

评论
阅读 219
1 个回答
撰写回答

登录后参与交流、获取后续更新提醒

宣传栏