本文深入剖析 JavaScript 中 Array.sort 方法的底层实现。通过分析 V8 引擎源码，揭示了其采用的快速排序算法及其多项优化策略，包括原地分区、三数取中法选取基准、重复元素处理、小数组切换选择排序以及减少递归深度的尾递归优化。文章还介绍了内省排序（Introsort）的概念，帮助开发者理解为何可以放心使用 Array.sort 处理大规模数据。
JavaScript 数组 sort 方法概述
在 JavaScript 中，数组对象提供了一个名为 sort 的方法，它接收一个函数作为参数来决定排序规则。开发者只需定义两个值的比较逻辑，无需关心内部排序机制。不过，了解 sort 的内部实现机制并非无益，深入探究其工作原理有助于更好地掌握这一工具。
在算法课程中，我们接触过冒泡、选择、快速、堆排序等多种算法。JavaScript 的 sort 方法具体采用了哪种算法？为了弄清这一点，直接查阅 V8 引擎的源代码是最直接的方式。V8 中 Array.sort 的实现由 JavaScript 编写，初步观察发现其使用了快速排序算法，但逻辑比常规实现更为复杂。这种复杂性源于何处，又为何必要，正是本文探讨的核心。
快速排序算法原理
快速排序算法
快速排序之所以得名，是因为其最佳和平均时间复杂度均为 O(nlogn)，应用极为广泛。其原理并不复杂：首先选取一个基准元素（pivot，可以是任意元素），然后将所有元素与基准比较，小于基准的放入一个集合，其余放入另一个集合；接着对这两个集合递归执行快速排序，最终得到完全有序的序列。
因此，快速排序的核心在于不断将原数组切割成小数组，并对这些小数组进行相同处理，这是一种典型的分治算法设计思路。实现一个简易的快速排序并不困难，我们可以尝试如下代码：
function QuickSort(arr, func) {
if (!arr || !arr.length) return [];
if (arr.length === 1) return arr;
var pivot = arr[0];
var smallSet = [];
var bigSet = [];
for (var i = 1; i < arr.length; i++) {
if (func(arr[i], pivot) < 0) {
smallSet.push(arr[i]);
} else {
bigSet.push(arr[i]);
}
}
return QuickSort(smallSet, func).concat([pivot]).concat(QuickSort(bigSet, func));
}这是一个非常基础的实现，选取数组的第一项作为基准元素。
原地排序与分区实现
原地（in-place）排序
观察上述算法，我们发现它创建了新数组来存储计算结果，从空间利用角度看并不经济。JavaScript 的快速排序实现并未创建新数组，而是在原数组基础上通过交换元素位置来完成排序。因此，与 push、pop、splice 等方法类似，sort 方法会直接修改原数组对象。
前文提到快速排序的核心是切割数组。若仅在原数组上交换元素，如何实现切割？实际上，我们无需真正切割数组，只需记录每个部分的起止索引即可。例如，假设数组为 [12, 4, 9, 2, 18, 25]，选取第一项 12 为基准，按原始快速排序算法，数组会被切割成 [4, 9, 2], 12, [18, 25]。但我们可以通过比较和交换，将原数组修改为 [4, 9, 2, 12, 18, 25]，然后根据基准元素 12 的位置，将 0~2 号元素视为一组，4~5 号元素视为另一组。为便于表述，我们将比基准元素小的元素组成的分区称为小数分区，另一个分区称为大数分区。这类似于电脑硬盘分区，并非物理分割，而是逻辑上的划分。在快速排序中，这一过程被称为分区（partition）。因此，我们需要修正之前的说法：快速排序的核心是分区。
说了这么多，还是实现一个带分区的快速排序吧：
function swap(arr, from, to) {
if (from == to) return;
var temp = arr[from];
arr[from] = arr[to];
arr[to] = temp;
}
function QuickSortWithPartition(arr, func, from, to) {
if (!arr || !arr.length) return [];
if (arr.length === 1) return arr;
from = from || 0;
to = to || arr.length - 1;
var pivot = arr[from];
var smallIndex = from;
var bigIndex = from + 1;
for (; bigIndex <= to; bigIndex++) {
if (func(arr[bigIndex], pivot) < 0) {
smallIndex++;
swap(arr, smallIndex, bigIndex);
}
}
swap(arr, smallIndex, from);
QuickSortWithPartition(arr, func, from, smallIndex - 1);
QuickSortWithPartition(arr, func, smallIndex + 1, to);
return arr;
}代码看似变长，但逻辑并不复杂。首先，由于涉及元素交换，需先实现一个 swap 方法来处理交换操作。快速排序算法中增加了 from 和 to 两个参数，分别表示当前处理的数组起始索引和终止索引；若这两个参数缺失，则表示处理整个数组。
同样，这里采用最简单的方式选取基准元素，即所要处理分区的第一个元素。接着定义 smallIndex 和 bigIndex 两个变量，分别表示左侧小数分区的终止索引和右侧大数分区的终止索引。这意味着从第一个元素（基准元素）到第 smallIndex 个元素间的所有元素都比基准元素小，从第 smallIndex + 1 到第 bigIndex 个元素都比基准元素大。初始时，这两个分区均为空。比较过程很简单，bigIndex 向右移动直至分区尾部。每当 bigIndex 增加 1，我们会判断该位置元素是否比基准元素大；如果是，无需处理，它已处于大数分区；如果比基准小，则需进行一次交换。具体操作是：首先将 smallIndex 增加 1，意味着小数分区增加了一个元素，但此时 smallIndex 位置的元素是一个大数（若之前大数分区为空，smallIndex 和 bigIndex 相等，但这不影响交换结果），而 bigIndex 位置的元素是一个小数，因此只需交换这两个位置的元素即可。
最后，别忘了初始的起始元素，其位置并不正确，只需将其与 smallIndex 位置的元素交换即可。此时，我们得到了对应的小数分区 [from...smallIndex - 1] 和大数分区 [smallIndex + 1...to]。再对这两个分区递归排序即可。
分区过程的优化策略
分区过程的优化
上述分区过程仍有优化空间，因为大数分区和小数分区都是从左向右增长。我们可以考虑从两侧向中间遍历，这样能有效减少交换元素的次数。例如，对于数组 [2, 1, 3, 1, 3, 1, 3]，采用上述分区算法，共遇到三次比基准元素小的情况，发生三次交换；而若换个思路，从右往左找到小于基准的元素，与从左往右找到大于基准的元素交换，该数组只需交换一次，即把第一个 3 和最后一个 1 交换。
我们也来尝试写一下实现：
function QuickSortWithPartitionOp(arr, func, from, to) {
if (!arr || !arr.length) return [];
from = from || 0;
to = to || arr.length - 1;
if (from >= to - 1) return arr;
var pivot = arr[from];
var smallEnd = from + 1;
var bigBegin = to;
while (smallEnd < bigBegin) {
while (func(arr[bigBegin], pivot) > 0 && smallEnd < bigBegin) {
bigBegin--;
}
while (func(arr[smallEnd], pivot) < 0 && smallEnd < bigBegin) {
smallEnd++;
}
if (smallEnd < bigBegin) {
swap(arr, smallEnd, bigBegin);
}
}
swap(arr, smallEnd, from);
QuickSortWithPartitionOp(arr, func, from, smallEnd - 1);
QuickSortWithPartitionOp(arr, func, smallEnd + 1, to);
return arr;
}分区性能与基准元素选取
分区与性能
前文提到，快速排序算法平均时间复杂度是 O(nlogn)，但在最差情况下时间复杂度会退化到 O(n^2)。性能好坏的关键在于分区是否合理。如果每次都能平均分成相等的两个分区，则只需 logn 层迭代；而如果每次分区都不合理，总有一个分区为空，则需要 n 层迭代，这是性能最差的场景。
那么性能最差的场景会出现吗？对于内容随机的数组，不太可能出现最差情况。但我们平时编程时，处理的数组往往并非内容随机，而是可能预先有一定顺序。设想一下，如果一个数组已经排好序，由于之前的算法中均采用第一个元素作为基准元素，必然会出现每次分区都有一个分区为空的情况。这种情况当然需要避免。
一种简单的解决方法是不选取固定位置的元素作为基准元素，而是随机从数组中挑出一个元素作为基准。这种方法非常有效，极大概率地避免了最差情况。这种处理思想很简单，此处不再赘述代码。
然而，极大概率地避免最差情况并不等于完全避免，特别是对于数组很大的时候，更要求我们在选取基准元素时要更加谨慎。
三数取中（median-of-three）
基准元素应当精心挑选，而挑选基准元素的一种方法为三数取中，即选取基准元素时，先把第一个元素、最后一个元素和中间一个元素挑出来，这三个元素中大小在中间的那个元素就被认为是基准元素。
简单实现一下获取基准元素的方法：
function getPivot(arr, func, from, to) {
var middle = (from + to) >> 1;
var i0 = arr[from];
var i1 = arr[to];
var i2 = arr[middle];
var temp;
if (func(i0, i1) > 0) {
temp = i0;
i0 = i1;
i1 = temp;
}
if (func(i0, i2) > 0) {
arr[middle] = i0;
arr[from] = i2;
arr[to] = i1;
return i0;
} else {
arr[from] = i0;
if (func(i1, i2) > 0) {
arr[middle] = i1;
arr[to] = i2;
return i1;
} else {
arr[middle] = i2;
arr[to] = i1;
return i2;
}
}
}这个例子里我完全没管基准元素的位置，一是降低复杂度，另一个原因是下面讨论重复元素处理时，基准元素的位置没什么意义。不过我把最小的值赋给了第一个元素，最大的值赋给了第二个元素，后面处理重复元素时会有帮助。
当然，仅仅是三数取中获得的基准元素，也不见得是可靠的。于是有一些其他的取中值的方法出现。有几种比较典型的手段，一种是平均间隔取一个元素，多个元素取中位数（即多取几个，增加可靠性）；一种是对三数取中进行递归运算，先把大数组平均分成三块，对每一块进行三数取中，会得到三个中值，再对这三个中值取中位数。
不过查阅 v8 的源代码，发现 v8 的基准元素选取更为复杂。如果数组长度不超过 1000，则进行基本的三数取中；如果数组长度超过 1000，那么 v8 的处理是除去首尾的元素，对剩下的元素每隔 200 左右（200~215，并不固定）挑出一个元素。对这些元素排序，找出中间的那个，并用这个元素跟原数组首尾两个元素一起进行三数取中。这段代码我就不写了。
重复元素的处理机制
针对重复元素的处理
到目前为止，我们在处理元素比较的时候比较随意，并没有太多地考虑元素相等的问题。但实际上我们做了这么多性能优化，对于重复元素引起的性能问题并没有涉及到。重复元素会带来什么问题呢？设想一下，一个数组里如果所有元素都相等，基准元素不管怎么选都是一样的。那么在分区的时候，必然出现除基准元素外的其他元素都被分到一起去了，进入最差性能的 case。
那么对于重复元素应该怎么处理呢？从性能的角度，如果发现一个元素与基准元素相同，那么它应该被记录下来，避免后续再进行不必要的比较。所以还是得改分区的代码。
function QuickSortWithPartitionDump(arr, func, from, to) {
if (!arr || !arr.length) return [];
from = from || 0;
to = to || arr.length - 1;
if (from >= to - 1) return arr;
var pivot = getPivot(arr, func, from, to);
var smallEnd = from;
var bigBegin = to;
for (var i = smallEnd + 1; i < bigBegin; i++) {
var order = func(arr[i], pivot);
if (order < 0) {
smallEnd++;
swap(arr, i, smallEnd);
} else if (order > 0) {
while (bigBegin > i && order > 0) {
bigBegin--;
order = func(arr[bigBegin], pivot);
}
if (bigBegin == i) break;
swap(arr, i, bigBegin);
if (order < 0) {
swap(arr, i, smallEnd);
smallEnd++;
}
}
}
QuickSortWithPartitionDump(arr, func, from, smallEnd);
QuickSortWithPartitionDump(arr, func, bigBegin, to);
return arr;
}简单解释一下这段代码，上文已经说过，在 getPivot 方法中，我将比基准小的元素放到第一位，把比基准大的元素放到最后一位。定义三个变量 smallEnd、bigBegin、i，从 from 到 smallEnd 之间的元素都比基准元素小，从 smallEnd 到 i 之间的元素都和基准元素一样大，从 i 到 bigBegin 之间的元素都是还没有比较的，从 bigBegin 到 to 之间的元素都比基准元素大。了解这个关系就好理解这段代码了。遍历从 smallEnd + 1 到 bigBegin 之间的元素： * 如果这个元素小于基准，那么 smallEnd 增加 1，这时 smallEnd 位置的元素是等于基准元素的（或者此时 smallEnd 与 i 相等），交换 smallEnd 与 i 处的元素就可以了。 * 如果这个元素大于基准，相对比较复杂一点。此时让 bigBegin 减小 1，检查大数分区前面一个元素是不是大于基准，如果大于基准，重复此步骤，不断让 bigBegin 减小 1，直到找到不比基准大的元素（如果这个过程中，发现 bigBegin 与 i 相等，则中止遍历，说明分区结束）。找到这个不比基准大小元素时需要区分是不是比基准小。如果比基准小，需要做两步交换，先将 i 位置的大数和 bigBegin 位置的小数交换，这时跟第一种 case 同时，smallEnd 增加 1，并且将 i 位置的小数和 smallEnd 位置的元素交换。如果和基准相等，则只需要将 i 位置的大数和 bigBegin 位置的小数交换。 * 如果这个元素与基准相等，什么也不用做。
小数组与递归深度优化
小数组优化
对于小数组（小于 16 项或 10 项。v8 认为 10 项以下的是小数组。），可能使用快速排序的速度还不如平均复杂度更高的选择排序。所以对于小数组，可以使用选择排序法要提高性能，减少递归深度。
function insertionSort(a, func, 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];
if (func(tmp, element) > 0) {
a[j + 1] = tmp;
} else {
break;
}
}
a[j + 1] = element;
}
}V8 引擎的额外优化与总结
v8 引擎没有做的优化
由于快速排序的不稳定性（少数情况下性能差，前文已经详细描述过），David Musser 于 1997 设计了内省排序法（Introsort）。这个算法在快速排序的基础上，监控递归的深度。一旦长度为 n 的数组经过了 logn 层递归（快速排序算法最佳情况下的递归层数）还没有结束的话，就认为这次快速排序的效率可能不理想，转而将剩余部分换用其他排序算法，通常使用堆排序算法（Heapsort，最差时间复杂度和最优时间复杂度均为 nlogn）。
v8 引擎额外做的优化
快速排序递归很深，如果递归太深的话，很可以出现“爆栈”，我们应该尽可能避免这种情况。上面提到的对小数组采用选择排序算法，以及采用内省排序算法都可以减少递归深度。不过 v8 引擎中，做了一些不太常见的优化，每次我们分区后，v8 引擎会选择元素少的分区进行递归，而将元素多的分区直接通过循环处理，无疑这样的处理大大减小了递归深度。我大致把 v8 这种处理的过程写一下：
function quickSort(arr, from, to){
while(true){
// 排序分区过程省略
// ...
if (to - bigBegin < smallEnd - from) {
quickSort(a, bigBegin, to);
to = smallEnd;
} else {
quickSort(a, from, smallEnd);
from = bigBegin;
}
}
}不得不说是一个很巧妙的实现。
总结
不知不觉这篇文章写了这么长。本来想对比各种优化之间的性能差异，现在看来也没有什么必要。虽然快速排序算法是一个很容易很基础的算法，但我相信很多人并没有能够这么深入地去了解、去优化一个算法。而读过了 v8 引擎对于这么一个简单算法的实现后，我发现它并没有简单地为了实现一个算法而去实现，而是确确实实地尽一切可能去提高算法效率，去消除可能引起性能问题的因素。结论是你真的可以放心地使用 Array.sort 方法，它的性能令人放心。那么剩下问题的就是：作为开发者，我们应该如何编写。
本文基于署名-非商业性使用 3.0 许可协议发布，转载、演绎必须保留本文的署名周骅，且不得用于商业目的。如您有任何疑问或者授权方面的协商，请与我联系。