javascript - 用JavaScript排序:返回 bool 值是否足以用作比较函数？

Question

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

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

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

Answer 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 method可以使用可选的自定义比较函数作为其参数。该函数采用两个参数（通常称为a和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 spec on sort（与ES6 spec中的内容相同）：


  如果comparefn不是此数组元素的一致比较函数，则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)和v作为其两个参数时，调用a始终返回相同的值b。此外，Type(v)是Number，而v不是NaN。请注意，这意味着对于给定的a <CF b和a =CF b对，a >CF b，a和b中的一个完全正确。
  
  
  调用comparefn(a,b)不会修改此对象。
  a =CF a（reflexivity）
  如果为a =CF b，则为b =CF a（symmetry）
  如果为a =CF b和b =CF c，则为a =CF c（=CF中的transitivity）
  如果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

哎呀这就是为什么在使用不一致的比较函数调用排序算法时会失败的原因（在规范中，这是“实现相关的行为”，即结果无法预测）。


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


因为在许多其他语言中，有一些排序算法不期望three-way comparison而是布尔布尔小于运算符。 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)}。

For numbers，您只需返回它们的差，即遵守上述所有定律：

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

如果要反向排序，只需选择适当的一个，然后将a与b交换。

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