一尘不染

用JavaScript排序：返回布尔值是否足以用作比较函数？

javascript

我总是成功地对数组进行如下排序（当我不希望使用标准字典顺序时）：

var arr = […] // some numbers or so
arr.sort(function(a, b) {
    return a > b;
});

现在，有人告诉我这是错误的，我需要return a-b代替。是真的，如果是，为什么呢？我已经测试了比较功能，并且可以正常工作！此外，为什么我的解决方案错了会如此普遍？

阅读 724

2020-04-22

共1个答案

一尘不染

TL; DR

我总是这样成功地排序我的数组

不，你没有。并没有注意到它。一个简单的反例：

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

为什么？

因为即使大于，比较函数也确实会返回false（或0等效地）。但是暗示着这两个元素被认为是相等的-排序算法相信这一点。b``a``0

深入解释

JavaScript中的比较功能

比较功能如何工作？

该Array::sort方法可以将可选的自定义比较函数作为其参数。该函数接受两个参数（通常称为aand
b）进行比较，并应返回一个数字

> 0当a被认为大于b并且应该在其后进行排序
== 0什么时候a被认为等于，b而先到是无关紧要的
< 0当a被认为是小于b，并应该在其之前进行排序

如果不返回数字，则结果将强制转换为数字（对于布尔值来说很方便）。返回的数字不一定要是-1或0或1（尽管通常是）。

一致的订购

为了保持一致，比较函数需要满足以下等式

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规范sort与[ES6规范相同）：

如果comparefnis […]不是此数组元素的一致比较函数，则sort的行为由实现定义。

_函数comparefn是一组值的一致的比较函数S，如果所有的下面都满足所有值的要求a，b以及c在所述一组（可能是相同的值）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)总是返回相同的值。此外，是Number，不是。请注意，这意味着恰好一个，和将是真正的一对给定的和。v``a``b``Type(v)``v``NaN``a <CF b``a =CF b``a >CF b``a``b

调用comparefn(a,b)不会修改此对象。

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，则a <CF c（的传递性为<CF）

如果a >CF b和b >CF c，则a >CF c（的传递性为>CF）

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

嗯，这是什么意思？我为什么要在乎？

排序算法需要将数组的各项相互比较。为了做好一项高效的工作，它不必将每个项目都进行比较，而需要能够推断出它们的顺序。为使此功能正常运行，需要遵循一些规则，自定义比较功能必须遵守。一个不重要的问题是，某项a等于其自身（compare(a, a) == 0）-这是上面列表中的第一项（反射性）。是的，这有点数学，但值得。

最重要的是传递性。它说，当算法已经比较两个值a和b，并b用c，并通过应用比较函数如发现a = b和b < c，然后
就可以预期 的是a < 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)
}

如果你想反向排序，只取一个合适的交换和a使用b。

如果你想复合类型（对象等）进行排序，替换每个a每个b与性能问题的访问，还是一个方法调用或任何你想进行排序。

2020-04-22