为什么使用

Question

在JavaScript中对一组数字进行排序时，我不小心使用了< code >

例：

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

如果我们分析正在做的事情，似乎这主要是运气，因为在这种情况下，3 和 2 被认为是“相同的”，应该是可以互换的。我想在这种情况下，JS 引擎会保留任何被视为相等的值的原始顺序：

let a = [1, 3, 2, 4];
a.sort((n1, n2) => {
  const result = n1 < n2;
  if (result < 0) {
    console.log(`${n1} comes before ${n2}`);
  } else if (result > 0) {
    console.log(`${n2} comes before ${n1}`);
  } else {
    console.log(`${n1} comes same position as ${n2}`);
  }
  return result;
})

console.log(a);

Answer 2

在我最初的评论之后，我想知道找到这种排序方法失败的数组有多容易。

我对长度不超过8的数组进行了彻底的搜索(在一个与数组大小相同的字母表上)，但一无所获。由于我的(公认的低劣)算法开始太慢，我将它改为大小为2的字母表，并发现长度不超过10的二进制数组都可以正确排序。然而，对于长度为11的二进制数组，许多排序不正确，例如< code>[0，1，1，1，1，1，1，1，1，1，0]。

// Check if 'array' is properly sorted using the "<" comparator function
function sortWorks(array) {
    let sorted_array = array.sort(function(n1, n2) {
        return n1 < n2;
    });
    for (let i=0; i<sorted_array.length-1; i++) {
        if (sorted_array[i] < sorted_array[i+1]) return false;
    }
    return true;
}

// Get a list of all arrays of length 'count' on an alphabet of size 'max_n'.
// I know it's awful, don't yell at me :'(
var arraysGenerator;
arraysGenerator = function (max_n, count) {
    if (count === 0) return [[]];
    let arrays = arraysGenerator(max_n, count-1);
    let result = [];
    for (let array of arrays) {
        for (let i = 0; i<max_n; i++) {
            result.push([i].concat(array));
        }
    }
    return result;
}

// Check if there are binary arrays of size k which are improperly sorted,
// and if so, log them
function testArraysOfSize(k) {
    let arrays = arraysGenerator(2, k);
    for (let array of arrays) {
        if (!sortWorks(array)) {
            console.log(array);
        }
    }
}

但由于某种原因，我得到了一些奇怪的误报，不知道我的错误在哪里。

编辑：

检查了一会儿后，这里部分解释了为什么OP的“错误”排序方法适用于长度

来源：这里，感谢原作者。

Answer 3

这种排序在您的输入数组上有效，因为它的大小很小，而且当前在ChromeV8（可能还有其他浏览器）中实现了sort。

比较器函数的返回值在文档中定义：

• 如果 compareFunction（a， b） 小于 0，则将 a 排序为小于 b 的索引，即 a 排在第一位。
• 如果 compareFunction（a， b） 返回 0，则保持 a 和 b 彼此不变，但相对于所有不同的元素进行排序。
• 如果 compareFunction（a， b） 大于 0，则排序 b 到小于 a 的索引，即 b 排在第一位。

但是，您的函数返回二进制 true 或 false，与数字相比，它们的计算结果分别为 1 或 0。这有效地将比较归结为n1

如果数组小于11个元素，ChromeV8的排序例程会立即切换到插入排序，并且不执行快速排序步骤：

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

V8 的插入排序实现只关心比较器函数是否将 b 报告为大于 a，对 0 和

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

然而，在选择数据透视点和分区时，快速排序的实现依赖于所有三个比较：

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 个以上元素的数组至少要有一个几乎肯定不准确的快速排序步骤。

更新7/19/19：由于本文中讨论了V8（6）的版本，V8的数组排序的实现在7.0中移动到了Torque/Timsort，正如本文中所讨论的，插入排序在长度为22或更小的数组上调用。

上面链接的文章描述了问题发生时V8排序的历史情况：

< code > array . prototype . sort 和< code > typed array . prototype . sort 依赖于用JavaScript编写的相同快速排序实现。排序算法本身相当简单:其基础是快速排序，对于较短的数组(长度

不管实现细节有什么变化，如果排序比较器遵循标准，代码将按可预测的方式排序，但如果比较器没有履行约定，所有的赌注都将落空。