TL的;博士

我总是像这样成功地对我的数组进行排序

不，你没有。并没有注意到它。一些快速的反例：

> [0,1,0].sort(function(a,b){ return a>b })
Array [0, 1, 0] // in Chrome, in Internet Exploder 11.
// Results may vary between sorting algorithm implementations
> [1,1,0,2].sort(function(a, b){ return a>b })
Array [0, 1, 2, 1] // in Opera 12.
Array [1, 1, 0, 2] // in Chrome 100, in Internet Exploder 11.
// Results will vary between sorting algorithm implementations

为什么？

因为您的比较函数确实返回（或等效地），即使大于 。但意味着这两个元素被认为是相等的——并且排序算法相信这一点。false0ba0

深度讲解

JavaScript 中的比较函数

比较函数如何工作？

Array：：sort 方法可以采用可选的自定义比较函数作为其参数。该函数接受两个参数（通常称为 和 ），它应该比较它们，并应该返回一个数字ab

• > 0when 被认为大于 and should be sort after itab
• == 0当被认为是等于的，哪个先来并不重要ab
• < 0当被认为小于 并且应该在它之前排序ab

如果它没有返回一个数字，则结果将被强制转换为一个数字（这对于布尔值来说很方便）。返回的数字不需要完全是 or 或（尽管它通常是）。-101

一致的订购

为了保持一致，比较函数需要满足方程

comp(a, b) == -1 * comp(b, a)
// or, if values other than -1, 0 and 1 are considered:
comp(a, b) * comp(b, a) <= 0

如果违反该要求，则排序将表现为未定义。

引用 ES5.1 规范中的排序（与 ES6 规范相同）：

如果 comparefn 不是此数组元素的一致比较函数，则排序行为是实现定义的。

如果集合 S 中的所有值 a、b 和 c（可能相同值）都满足以下所有要求，则函数 comparefn 是一组值 S 的一致比较函数：符号 a <CF b 表示 comparefn（a，b） < 0;a =CF b 表示 comparefn（a，b） = 0 （任一符号）;a >CF b 表示 comparefn（a，b） > 0。

调用 comparefn（a，b） 时，当给定一对特定的值 a 和 b 作为其两个参数时，始终返回相同的值 v。此外，Type（v） 是 Number，而 v 不是 NaN。请注意，这意味着对于给定的 a 和 b 对，a <CF b、a =CF b 和 >CF b 中的一个将成立。

• 调用 comparefn（a，b） 不会修改 this 对象。
• a =CF a（反身性）
• 如果 a =CF b，则 b =CF a（对称）
• 如果 a =CF b 和 b =CF c，则 a =CF c（=CF 的传递性）
• 如果 a <CF b 和 b <CF c，则 <CF c（传递性为 <CF）
• 如果 a >CF b 和 b >CF c，则 >CF c（传递性为 >CF）

注意：上述条件是必要且充分的，以确保 comparefn 将集合 S 划分为等价类，并且这些等价类是完全有序的。

呃，这是什么意思？我为什么要关心？

排序算法需要将数组中的项相互比较。要做好高效的工作，它一定不需要将每个项目相互比较，而是需要能够推理它们的顺序。为了正常工作，自定义比较函数需要遵守一些规则。一个微不足道的问题是，一个项目等于它自己（）——这是上面列表中的第一项（反身性）。是的，这有点数学化，但回报很高。acompare(a, a) == 0

最重要的一个是传递性。它说，当算法比较了两个值 和 时，也比较了 ，并且通过应用比较函数发现，例如 和 ，那么它也可以预期也成立。这似乎是合乎逻辑的，并且是定义明确、一致的排序所必需的。abbca = bb < ca < c

但是您的比较函数确实无法做到这一点。让我们看一下这个例子：

 function compare(a, b) { return Number(a > b); }
 compare(0, 2) == 0 // ah, 2 and 0 are equal
 compare(1, 0) == 1 // ah, 1 is larger than 0
 // let's conclude: 1 is also larger than 2

哎呀。这就是为什么当排序算法使用不一致的比较函数调用时，它可能会失败（在规范中，这是“依赖于实现的行为”——即不可预测的结果）。

为什么错误的解决方案如此普遍？

因为在许多其他语言中，有些排序算法不需要三向比较，而只是一个布尔小于运算符。C++ std：：sort 就是一个很好的例子。如果需要确定相等性，它将简单地应用两次，并交换参数。诚然，这可能更有效，更不容易出错，但如果无法内联运算子，则需要对比较函数进行更多调用。

反例

我已经测试了我的比较功能，它有效！

只是纯粹靠运气，如果你尝试一些随机的例子。或者因为您的测试套件存在缺陷 - 不正确和/或不完整。

这是我用来找到上面最小反例的小脚本：

function perms(n, i, arr, cb) {
// calls callback with all possible arrays of length n
    if (i >= n) return cb(arr);
    for (var j=0; j<n; j++) {
        arr[i] = j;
        perms(n, i+1, arr, cb);
    }
}
for (var i=2; ; i++) // infinite loop
    perms(i, 0, [], function(a) {
        if (    a.slice().sort(function(a,b){ return a>b }).toString()
             != a.slice().sort(function(a,b){ return a-b }).toString() )
            // you can also console.log() all of them, but remove the loop!
            throw a.toString();
    });

什么比较函数是正确的？

当您想要词典排序时，根本不使用比较功能。如有必要，数组中的项将被字符串化。

与关系运算符类似工作的通用比较函数可以实现为

function(a, b) {
    if (a > b) return 1;
    if (a < b) return -1;
    /* else */ return 0;
}

通过一些技巧，这可以缩小到等效的.function(a,b){return +(a>b)||-(a<b)}

对于数字，您可以简单地返回它们的差值，这符合上述所有定律：

function(a, b) {
    return a - b; // but make sure only numbers are passed (to avoid NaN)
}

如果要反向排序，只需选择适当的排序并交换。ab

如果要对复合类型（对象等）进行排序，请将每个类型替换为相关属性的访问权限，或方法调用或要排序的任何内容。ab

sort 函数需要一个需要两个参数和 的函数，并返回：ab

• 如果 a 在 b 之前，则为负数
• 如果 a 在 b 之后，则为正数
• 如果 a 和 b 的相对顺序无关紧要，则为零

为了按升序对数字进行排序，将产生正确的返回值;例如：return a - b

a    b    ret
1    2    -1
3    2     1
2    2     0

另一方面，生成以下返回值：return a > b

a    b    ret      implied
1    2    false    0
3    2    true     1
2    2    false    0

在上面的例子中，排序函数被告知 1 和 2 是相同的（将 1 放在 2 之前或将 2 放在 1 之前无关紧要）。这将产生不正确的结果，例如（在 Chrome 49 中）：

console.log([5, 8, 7, 1, 2, 3, 4, 6, 9, 10, 11, 12, 13].sort(function(a, b) {
    return a > b;
}));
// [4, 5, 3, 1, 2, 6, 7, 8, 9, 10, 11, 12, 13]