36. 能不能实现数组sort方法？

// 判断 sealed 对象和 frozen 对象, 即密封对象和冻结对象 if (Object.isSealed(array) && deleteCount !== addElements.length) {

throw new TypeError('the object is a sealed object!')

} else if(Object.isFrozen(array) && (deleteCount > 0 || addElements.length > 0)) {

throw new TypeError('the object is a frozen object!')

}

// 拷贝删除的元素 sliceDeleteElements(array, startIndex, deleteCount, deleteArr);

// 移动删除元素后面的元素 movePostElements(array, startIndex, len, deleteCount, addElements);

// 插入新元素 for (let i = 0; i < addElements.length; i++) {

array[startIndex + i] = addElements[i];

}

array.length = len - deleteCount + addElements.length;

return deleteArr;

}

1. 能不能实现数组sort方法？

估计大家对 JS 数组的sort 方法已经不陌生了，之前也对它的用法做了详细的总结。那，它的内部是如何来实现的呢？如果说我们能够进入它的内部去看一看，理解背后的设计，会使我们的思维和素养得到不

错的提升。

sort 方法在 V8 内部相对与其他方法而言是一个比较高深的算法，对于很多边界情况做了反复的优化，但是这里我们不会直接拿源码来干讲。我们会来根据源码的思路，实现一个跟引擎性能一样的排序算

法，并且一步步拆解其中的奥秘。

V8 引擎的思路分析

首先大概梳理一下源码中排序的思路:

设要排序的元素个数是n：

当 n <= 10 时，采用插入排序

当 n > 10 时，采用

三路快速排序

10 < n <= 1000, 采用中位数作为哨兵元素 n > 1000, 每隔 200~215 个元素挑出一个元素，放到一个新数组，然后对它排序，找到中间

nlogn的优势会越来越小，倘若插入排序O(n^2)前面的系数足够小，那么就会超过快排。而事实上正是如此，插入排序经过优化以后对于小数据集的排序会有非常优越的性能，很多时候甚至会超过快排。

因此，对于很小的数据量，应用插入排序是一个非常不错的选择。

第二、为什么要花这么大的力气选择哨兵元素？

因为快速排序的性能瓶颈在于递归的深度，最坏的情况是每次的哨兵都是最小元素或者最大元素，那么进行partition(一边是小于哨兵的元素，另一边是大于哨兵的元素)时，就会有一边是空的，那么这么排下

去，递归的层数就达到了n, 而每一层的复杂度是O(n)，因此快排这时候会退化成O(n^2)级别。

这种情况是要尽力避免的！如果来避免？

就是让哨兵元素进可能地处于数组的中间位置，让最大或者最小的情况尽可能少。这时候，你就能理解 V8 里面所做的种种优化了。

接下来，我们来一步步实现的这样的官方排序算法。

插入排序及优化

最初的插入排序可能是这样写的:

const insertSort = (arr, start = 0, end) => { end = end || arr.length;

for(let i = start; i < end; i++) { let j;

for(j = i; j > start && arr[j - 1] > arr[j]; j --) { let temp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = temp;

} }

return;

}

看似可以正确的完成排序，但实际上交换元素会有相当大的性能消耗，我们完全可以用变量覆盖的方式来完成，如图所示:

优化后代码如下:

const insertSort = (arr, start = 0, end) => { end = end || arr.length;

for(let i = start; i < end; i++) { let e = arr[i];

let j;

for(j = i; j > start && arr[j - 1] > e; j --)

arr[j] = arr[j-1];

arr[j] = e;

} return;

}

接下来正式进入到 sort 方法。

寻找哨兵元素

sort的骨架大致如下:

Array.prototype.sort = (comparefn) => { let array = Object(this);

let length = array.length >>> 0;

return InnerArraySort(array, length, comparefn);

}

const InnerArraySort = (array, length, comparefn) => { // 比较函数未传入

if (Object.prototype.toString.call(callbackfn) !== "[object Function]") { comparefn = function (x, y) {

if (x === y) return 0;

//...

} const getThirdIndex = (a, from, to) => {

// 元素个数大于1000时寻找哨兵元素 }

const quickSort = (a, from, to) => { //哨兵位置

let thirdIndex = 0;

while(true) { if(to - from <= 10) {

insertSort(a, from, to);

return;

} if(to - from > 1000) {

thirdIndex = getThirdIndex(a, from , to);

}else { // 小于1000 直接取中点

thirdIndex = from + ((to - from) >> 2);

} }

//下面开始快排 }

}

先来把求取哨兵位置的代码实现一下:

const getThirdIndex = (a, from, to) => { let tmpArr = [];

// 递增量，200~215 之间，因为任何正数和15做与操作，不会超过15，当然是大于0的 let increment = 200 + ((to - from) & 15);

let j = 0;

from += 1;

to -= 1;

for (let i = from; i < to; i += increment) { tmpArr[j] = [i, a[i]];

j++;

} // 把临时数组排序，取中间的值，确保哨兵的值接近平均位置

tmpArr.sort(function(a, b) { return comparefn(a[1], b[1]);

});

let thirdIndex = tmpArr[tmpArr.length >> 1][0];

return thirdIndex;

}

完成快排

接下来我们来完成快排的具体代码：

const quickSort = (a, from, to) => { //...

// 上面我们拿到了thirdIndex // 现在我们拥有三个元素，from, thirdIndex, to

// 为了再次确保 thirdIndex 不是最值，把这三个值排序 [a[from], a[thirdIndex], a[to - 1]] = _sort(a[from], a[thirdIndex], a[to -

1]);

// 现在正式把 thirdIndex 作为哨兵 let pivot = a[thirdIndex];

// 正式进入快排 let lowEnd = from + 1;

let highStart = to - 1;

// 现在正式把 thirdIndex 作为哨兵, 并且lowEnd和thirdIndex交换 let pivot = a[thirdIndex];

a[thirdIndex] = a[lowEnd];

a[lowEnd] = pivot;

// [lowEnd, i)的元素是和pivot相等的 // [i, highStart) 的元素是需要处理的

for(let i = lowEnd + 1; i < highStart; i++) { let element = a[i];

let order = comparefn(element, pivot);

if (order < 0) { a[i] = a[lowEnd];

a[lowEnd] = element;

lowEnd++;

} else if(order > 0) { do{

highStart--;

if(highStart === i) break;

order = comparefn(a[highStart], pivot);

}while(order > 0)

// 现在 a[highStart] <= pivot // a[i] > pivot

// 两者交换 a[i] = a[highStart];

a[highStart] = element;

if(order < 0) { // a[i] 和 a[lowEnd] 交换

element = a[i];

a[i] = a[lowEnd];

a[lowEnd] = element;

lowEnd++;

} }

} // 永远切分大区间

if (lowEnd - from > to - highStart) { // 继续切分lowEnd ~ from 这个区间

to = lowEnd;

// 单独处理小区间

测试结果

测试结果如下:

一万条数据:

十万条数据:

一百万条数据:

一千万条数据:

结果仅供大家参考，因为不同的node版本对于部分细节的实现可能不一样，我现在的版本是v10.15。

从结果可以看到，目前版本的 node 对于有序程度较高的数据是处理的不够好的，而我们刚刚实现的排序通过反复确定哨兵的位置就能有效的规避快排在这一场景下的劣势。

最后给大家完整版的sort代码:

const sort = (arr, comparefn) => { let array = Object(arr);

let length = array.length >>> 0;

comparefn = function (x, y) { if (x === y) return 0;

x = x.toString();

y = y.toString();

if (x == y) return 0;

else return x < y ? -1 : 1;

};

} const insertSort = (arr, start = 0, end) => {

end = end || arr.length;

for (let i = start; i < end; i++) { let e = arr[i];

let j;

for (j = i; j > start && comparefn(arr[j - 1], e) > 0; j--)

arr[j] = arr[j - 1];

arr[j] = e;

} return;

} const getThirdIndex = (a, from, to) => {

let tmpArr = [];

// 递增量，200~215 之间，因为任何正数和15做与操作，不会超过15，当然是大于0的 let increment = 200 + ((to - from) & 15);

let j = 0;

from += 1;

to -= 1;

for (let i = from; i < to; i += increment) { tmpArr[j] = [i, a[i]];

j++;

} // 把临时数组排序，取中间的值，确保哨兵的值接近平均位置

tmpArr.sort(function (a, b) { return comparefn(a[1], b[1]);

});

let thirdIndex = tmpArr[tmpArr.length >> 1][0];

return thirdIndex;

};

const _sort = (a, b, c) => { let arr = [];

arr.push(a, b, c);

insertSort(arr, 0, 3);

return arr;

}

const quickSort = (a, from, to) => { //哨兵位置

let thirdIndex = 0;

while (true) { if (to - from <= 10) {

insertSort(a, from, to);

} let tmpArr = _sort(a[from], a[thirdIndex], a[to - 1]);

a[from] = tmpArr[0]; a[thirdIndex] = tmpArr[1]; a[to - 1] = tmpArr[2];

// 现在正式把 thirdIndex 作为哨兵 let pivot = a[thirdIndex];

[a[from], a[thirdIndex]] = [a[thirdIndex], a[from]];

// 正式进入快排 let lowEnd = from + 1;

let highStart = to - 1;

a[thirdIndex] = a[lowEnd];

a[lowEnd] = pivot;

// [lowEnd, i)的元素是和pivot相等的 // [i, highStart) 的元素是需要处理的

for (let i = lowEnd + 1; i < highStart; i++) { let element = a[i];

let order = comparefn(element, pivot);

if (order < 0) { a[i] = a[lowEnd];

a[lowEnd] = element;

lowEnd++;

} else if (order > 0) { do{

highStart--;

if (highStart === i) break;

order = comparefn(a[highStart], pivot);

}while (order > 0) ;

// 现在 a[highStart] <= pivot // a[i] > pivot

// 两者交换 a[i] = a[highStart];

a[highStart] = element;

if (order < 0) { // a[i] 和 a[lowEnd] 交换

element = a[i];

a[i] = a[lowEnd];

a[lowEnd] = element;

lowEnd++;

} }

} // 永远切分大区间

if (lowEnd - from > to - highStart) { // 单独处理小区间

quickSort(a, highStart, to);

// 继续切分lowEnd ~ from 这个区间 to = lowEnd;

} else if (lowEnd - from <= to - highStart) { quickSort(a, from, lowEnd);

from = highStart;

} }