深入解析 V8 中 sort 的工作原理
背景
由一道算法题引起的思考。
之前在 leetcode 刷题的时候遇到这道题（题目来源寻找两个有序数组的中位数）
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5当初做的时候没有认真审题，直接两个数组合并然后排序再取中位数，提交的时候也直接 AC 了。后来看解析的时候发现有人吐槽 js 直接用 sort，耍赖皮，我才发现，原来题目要求时间复杂度为 O(log(m + n))。
那么问题来了，排序最快也要 O(nlogn)，那为何不会超时呢？
先看下我不审题的解答
var findMedianSortedArrays = function(nums1, nums2) {let num = nums1.concat(nums2);
num = num.sort((a, b) => a - b);
let mid = Math.floor(num.length / 2);
if (num.length % 2 === 0) {return (num[mid-1] + num[mid])/2
} else {return num[mid]
}
};我这里用的是 V8 优化过后的 sort 而不是普通的快排，那么是不是证明 V8 的 sort 要比快排还要快呢？
V8 中的 sort 与快速排序比较
这里我写了一个脚本，用来比较两个算法的运行时长
var quickSort = function (arr) {if (arr.length <= 1) {return arr;}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++) {if (arr[i] < pivot) {left.push(arr[i]);
} else {right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
let arr = [], brr = [], idx = 0, length = Math.floor(Math.random() * 10000000);
while (idx < length) {arr[idx] = brr[idx] = Math.floor(Math.random() * length);
idx++;
}
console.log('length===', length)
console.time('quicksort')
quickSort(arr)
console.timeEnd('quicksort')
console.time('V8_sort')
brr.sort((a, b) => {return a - b})
console.timeEnd('V8_sort')
我们可以看到结果，无论随机数组的长度如何，显然 V8 提供的 sort 是要比快排快的（可能有人吐糟我的快排有问题，快排写法取自阮一峰老师的博客，可能又有杠精要说阮一峰老师的快排是非原地快排，好的，请出门左拐，不送）
快排原理
这里先给大家补习一下快排的原理，熟悉的同学可以直接到下一标题。
原理
①选择一个元素作为 ” 基准 ”
②小于 ” 基准 ” 的元素，都移到 ” 基准 ” 的左边；大于 ” 基准 ” 的元素，都移到 ” 基准 ” 的右边。
③对 ” 基准 ” 左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
示例
以下示例取自阮一峰老师的博客快速排序（Quicksort）的 Javascript 实现
举例来说，现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50}，怎么对其排序呢？
第一步，选择中间的元素 45 作为 ” 基准 ”。（基准值可以任意选择，但是选择中间的值比较容易理解。）
第二步，按照顺序，将每个元素与 ” 基准 ” 进行比较，形成两个子集，一个 ” 小于 45″，另一个 ” 大于等于 45″。
第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
V8 中 sort 原理
其中 V8 中的 sort 并不是单一的一种排序方法，而是根据数组长度来选择具体的方法，当数组长度小于等于 22，选择用插入排序，大于 22 则选择快速排序，源码中是这样写到：
// In-place QuickSort algorithm.
// For short (length <= 22) arrays, insertion sort is used for efficiency.插入排序其实没什么好说的，本文就此略过。
那么我们重点来看 V8 中 sort 的快速排序是怎么实现的。
基准的选择
先看源码
if (to - from <= 10) {InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {third_index = GetThirdIndex(a, from, to);
} else {third_index = from + ((to - from) >> 1);
}①当数组长度小于等于 10，剩下的数组直接用插入排序
②当数组长度大于 10 小于等于 1000 时，third_index = from + ((to - from) >> 1);
③当数组长度大于 1000 时，通过以下函数获取
var GetThirdIndex = function(a, from, to) {var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function(a, b) {return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}这里补充一下 from + ((to - from) >> 1) 和200 + ((to - from) & 15)中的 & 和 >>：
①&：按位与运算符“&”是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位都为 1 时，结果位才为 1。参与运算的两个数均以补码出现。
规则：
1&1=1
1&0=0
0&1=0
0&0=0例如：
3：0000 0011
5：0000 0101
得到的结果是：1：0000 0001
所以 3 & 5 = 1②>>: 按照二进制把数字右移指定数位，符号位为正补零，符号位负补一，低位直接移除。
例如：
let a = 60;
(60: 0011 1100)
a >> 2 之后等于 15
(15: 0000 1111)源码解析
源码太长，我们在这就不一行一行地过，直接贴上比较关键的代码，有兴趣的同学可以去看 github 上面的源码 V8 sort 源码，建议从第 710 行开始看
if (!IS_CALLABLE(comparefn)) {comparefn = function (x, y) {if (x === y) return 0;
if (%_IsSmi(x) && %_IsSmi(y)) {return %SmiLexicographicCompare(x, y);
}
x = TO_STRING(x);
y = TO_STRING(y);
if (x == y) return 0;
else return x < y ? -1 : 1;
};
}
var InsertionSort = f用过 sort 的同学应该知道，该函数接收一个函数 comparefn 作为参数，若不传，则默认将元素以字符串的方式升序排序，如：
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 GetThirdIndex = function(a, from, to) {var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function(a, b) {return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}
var QuickSort = function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {InsertionSort(a, from, to);
return;
}
if (to - from > 1000) {third_index = GetThirdIndex(a, from, to);
} else {third_index = from + ((to - from) >> 1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// From low_end to i are elements equal to pivot.
// From i to high_start are elements that haven't been compared yet.
partition: for (var i = low_end + 1; i < high_start; i++) {var element = a[i];
var order = comparefn(element, pivot);
if (order < 0) {a[i] = a[low_end];
a[low_end] = element;
low_end++;
} else if (order > 0) {
do {
high_start--;
if (high_start == i) break partition;
var top_elem = a[high_start];
order = comparefn(top_elem, pivot);
} while (order > 0);
a[i] = a[high_start];
a[high_start] = element;
if (order < 0) {element = a[i];
a[i] = a[low_end];
a[low_end] = element;
low_end++;
}
}
}
if (to - high_start < low_end - from) {QuickSort(a, high_start, to);
to = low_end;
} else {QuickSort(a, from, low_end);
from = high_start;
}
}
};- 用上面所阐述的方法获取基准
- 将基准、第一个元素以及最后一个元素进行排序处理
- 分别从第二个元素往右遍历和倒数第二个元素往左遍历，获取基准左侧比基准大的数与基准右侧比基准大的数，然后交换位置，接着基准与交换后较小的数字互换位置。
- 继续遍历，继续交换，直至左游标与右游标相会。
- 这时，基准左侧均是比基准小的数，基准右侧均是比基准大的数，分拆为两个数组，再递归遍历重复上面所有步骤，直到递归的数组长度小于等于 10，便直接使用插入排序。
举个例子????：
现有一个数组let arr= [1, 3, 9, 7, 0, 5, 2, 10, 6, 8, 4];
- 首先执行 QuickSort 函数，from 是 0，to 是 11，数组长度为 11，基准为
0 + ((11 - 0) >> 1)等于 5 - 所以
a[from]也就是a[0]，a[to]也就是a[10]和基准a[5]三者之间比较大小，得到新的数组是[1, 3, 9, 7, 0, 4, 2, 10, 6, 8, 5]，其中a[from] == a[0] == 1，a[from] == a[10] == 5，基准值 a[5] == 4; - 基准与 a[to+1]互换，得到
[1, 4, 9, 7, 0, 3, 2, 10, 6, 8, 5] - 然后便进入 partition 循环，其中 a[low_end] = 9; a[high_start] = 8; 开始从 low_end 往右找比基准大的值 9，以及从 high_start 开始往左找比基准小的值 2，互换得到
[1, 4, 2, 7, 0, 3, 9, 10, 6, 8, 5] - 然后基准值与刚才的较小值互换，得到
[1, 2, 4, 7, 0, 3, 9, 10, 6, 8, 5]，接着重复步骤 4 - 然后遍历 7，7 与 3 互换得到
[1, 2, 4, 3, 0, 7, 9, 10, 6, 8, 5] - 紧接着基准与较小值互换
[1, 2, 3, 4, 0, 7, 9, 10, 6, 8, 5] - 最后得到
[1, 2, 3, 0, 4, 7, 9, 10, 6, 8, 5] - 可以看出，基准左侧为比基准小的数组，基准右侧为比基准大的数组，分别用 QuicSort 递归左侧数组和右侧数组，最后便得到结果。
总结
V8 中的 sort 并不是一种单纯的排序方式，而是结合了插入排序以及快速排序的函数，并且针对快排做了优化。
本人才疏学浅，若有错误之处，请指正，必定尽快更改。