V8 JavaScript引擎 Array.sort()函数粗略解读

需要根据源码解释,V8 Array源码:https://github.com/v8/v8/blob/master/src/js/array.js
714行,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函数采用的两种排序算法决定的。

Tag: none

Leave a new comment