V8 JavaScript引擎 Array.sort()函数粗略解读
需要根据源码解释,V8 Array源码:https://github.com/v8/v8/blob/master/src/js/array.js714
行,764
行很关键
714行是说如果传入的comparefn不可调用那么sort默认按照字符串字典序排序。
举例:
"use strict";
var arr = [10, 1, 25, 100, 40, 5];
function sortNumber(a, b) {
return a - b;
}
console.log(arr.sort(sortNumber(5, 2)));
//Result: [1, 10, 100, 25, 40, 5]
这时sort函数接受参数为sortNumber(5, 2)
已经调用完成,是一个数字而不是函数,所以结果按照字典序排序。
以上仅讨论了Array.sort();传入的为非正常比较函数的情况,下面讲另一处比较有意思的地方。
764行是说当数组长度length <= 10
的时候sort函数调用InsertionSort
插入排序(726行),如果长度length > 10
会调用QuickSort
快速排序(760行)
712行注释说length <= 22写错了,代码中实际是length <= 10
所以会有这样的结果:
1. 当待排序数组长度length <= 10
,compare函数返回 常数负数 或 常数0 时sort函数没有效果,compare函数返回常数正数sort函数对数组反向。这是由插入排序性质决定的。
compare函数返回常数负数或者常数0:
"use strict";
var arr = [7,8,9,10,11,3,4,5,6,];//12,13,14,15,16,11,18,19,20,21,22,23];
function sortNumber(a, b) {
console.log("a", a, " ", "b", b);
return 0;//or return -1;
}
console.log(arr.sort(sortNumber));
//Result: [7, 8, 9, 10, 11, 3, 4, 5, 6]
这种情况时数组顺序不变,从排序比较过程也可以看出是标准的插入排序算法。
a 7 b 8
a 8 b 9
a 9 b 10
a 10 b 11
a 11 b 3
a 3 b 4
a 4 b 5
a 5 b 6
compare函数返回常数正数:
"use strict";
var arr = [7,8,9,10,11,3,4,5,6,];//12,13,14,15,16,11,18,19,20,21,22,23];
function sortNumber(a, b) {
console.log("a", a, " ", "b", b);
return 1;
}
console.log(arr.sort(sortNumber));
//Result: [6, 5, 4, 3, 11, 10, 9, 8, 7]
2. 当待排序数组长度length > 10
,compare函数返回值是常数时返回的数组是乱序的。
"use strict";
var arr = [7,8,9,10,11,3,4,5,6,12,13,14,15,16,11,18,19,20,21,22,23];
function sortNumber(a, b) {
console.log("a", a, " ", "b", b);
return -1;
}
console.log(arr.sort(sortNumber));
//Result: [7, 5, 6, 12, 4, 14, 15, 16, 11, 18, 3, 19, 11, 20, 10, 21, 9, 22, 8, 23, 13]
比较顺序如下,从前几条比较结果来看有明显的快速排序递归调用的特点:
a 7 b 23
a 7 b 13
a 23 b 13
a 9 b 23
a 10 b 23
a 11 b 23
a 3 b 23
a 4 b 23
a 5 b 23
a 6 b 23
a 12 b 23
a 8 b 23
a 14 b 23
a 15 b 23
a 16 b 23
a 11 b 23
a 18 b 23
a 19 b 23
a 20 b 23
a 21 b 23
a 22 b 23
a 7 b 22
a 7 b 8
a 22 b 8
a 10 b 22
a 11 b 22
a 3 b 22
a 4 b 22
a 5 b 22
a 6 b 22
a 12 b 22
a 9 b 22
a 14 b 22
a 15 b 22
a 16 b 22
a 11 b 22
a 18 b 22
a 19 b 22
a 20 b 22
a 21 b 22
a 7 b 21
a 7 b 9
a 21 b 9
a 11 b 21
a 3 b 21
a 4 b 21
a 5 b 21
a 6 b 21
a 12 b 21
a 10 b 21
a 14 b 21
a 15 b 21
a 16 b 21
a 11 b 21
a 18 b 21
a 19 b 21
a 20 b 21
a 7 b 20
a 7 b 10
a 20 b 10
a 3 b 20
a 4 b 20
a 5 b 20
a 6 b 20
a 12 b 20
a 11 b 20
a 14 b 20
a 15 b 20
a 16 b 20
a 11 b 20
a 18 b 20
a 19 b 20
a 7 b 19
a 7 b 11
a 19 b 11
a 4 b 19
a 5 b 19
a 6 b 19
a 12 b 19
a 3 b 19
a 14 b 19
a 15 b 19
a 16 b 19
a 11 b 19
a 18 b 19
a 7 b 18
a 7 b 3
a 18 b 3
a 5 b 18
a 6 b 18
a 12 b 18
a 4 b 18
a 14 b 18
a 15 b 18
a 16 b 18
a 11 b 18
a 7 b 5
a 5 b 6
a 6 b 12
a 12 b 4
a 4 b 14
a 14 b 15
a 15 b 16
a 16 b 11
待排序数组长度不同导致结果不一致,是sort函数采用的两种排序算法决定的。