javascript - 为什么用 < 对 JS 数字数组排序有效？

Question

在 JavaScript 中对数字数组进行排序时，我不小心使用了 <而不是 the usual - -- 但它仍然有效。我想知道为什么？

例子:

var a  = [1,3,2,4]
a.sort(function(n1, n2){
    return n1<n2
})
// result is correct: [4,3,2,1]

还有一个这不起作用的示例数组(感谢 Nicolas 的示例):

[1,2,1,2,1,2,1,2,1,2,1,2]

Answer 1

这种排序适用于您的输入数组，因为它的尺寸小且当前实现了 sort在 Chrome V8(可能还有其他浏览器)中。

比较函数的返回值定义在documentation中:

• If compareFunction(a, b) is less than 0, sort a to an index lower than b, i.e. a comes first.
• If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements.
• If compareFunction(a, b) is greater than 0, sort b to an index lower than a, i.e. b comes first.

但是，您的函数返回二进制 true或 false ，计算结果为 1或 0分别与数字进行比较。这有效地集中了 n1 < n2 的比较。在与 n1 === n2 ，声称两者是偶数。如果n1是 9 和 n2是 3，9 < 3 === false或 0 .换句话说，您的排序让 9 和 3“彼此保持不变”，而不是坚持“将 9 排序到低于 3 的索引”。

如果您的数组少于 11 个元素，Chrome V8 的排序例程 switches immediately到insertion sort并且不执行 quicksort步骤:

// Insertion sort is faster for short arrays.
if (to - from <= 10) {
  InsertionSort(a, from, to);
  return;
}

V8 的 insertion sort implementation只关心比较函数是否报告 b大于 a , 采取相同的 else两个分支 0和 < 0比较器返回:

var order = comparefn(tmp, element);
if (order > 0) {
  a[j + 1] = tmp;
} else {
  break;
}

Quicksort's implementation ，但是，在选择枢轴和划分时都依赖于所有三个比较:

var order = comparefn(element, pivot);
if (order < 0) {
  // ...
} else if (order > 0) {
  // ...
}
// move on to the next iteration of the partition loop

这保证了对数组的准确排序，例如 [1,3,2,4] , 并且将具有超过 10 个元素的数组注定为至少一个几乎肯定是不准确的快速排序步骤。

---

2019 年 7 月 19 日更新:自此答案中讨论的 V8 (6) 版本以来，V8 数组排序的实现已移至 Torque。/Timsort在 7.0 中，如本 blog post 中所讨论并对 length 22 or less 的数组调用插入排序.

上面链接的文章描述了问题出现时 V8 排序的历史情况:

Array.prototype.sort and TypedArray.prototype.sort relied on the same Quicksort implementation written in JavaScript. The sorting algorithm itself is rather straightforward: The basis is a Quicksort with an Insertion Sort fall-back for shorter arrays (length < 10). The Insertion Sort fall-back was also used when Quicksort recursion reached a sub-array length of 10. Insertion Sort is more efficient for smaller arrays. This is because Quicksort gets called recursively twice after partitioning. Each such recursive call had the overhead of creating (and discarding) a stack frame.

无论实现细节有何变化，如果排序比较器符合标准，代码将按可预测的方式排序，但如果比较器不符合约定，所有赌注都将落空。