在JavaScript中排序:不应该返回一个布尔值足够的比较函数？

Question

我总是这样成功地对我的数组进行排序(当我不想要标准的词典排序时):

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

现在,有人告诉我这是错的,我需要return a-b改为.这是真的,如果是的话为什么？我测试了我的比较功能,它有效!另外,为什么我的解决方案在出错时会如此常见？

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方法可以使用可选的自定义比较函数作为其参数.该函数接受两个应该比较的参数(通常称为a和b),并且应该返回一个数字

• > 0当a被认为大于b并且应该在它之后排序
• == 0什么时候a被认为是相同的,b哪个先到后无关紧要
• < 0当a被认为小于b并且应该在它之前进行排序

如果它没有返回数字,结果将被转换为数字(这对于布尔值来说很方便).返回的数字不需要完全或者(-1或者通常是).01

一致的订购

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

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规范中的相同内容):

如果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)始终返回相同的值.此外,是数字,而不是.请注意,这暗示着只有一个,和将是真正的一对给定的和.vabType(v)vNaNa <CF ba =CF ba >CF bab

• 调用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与性能问题的访问,还是一个方法调用或任何你想要排序.

Answer 2

该sort功能预计需要两个参数的函数a和b,并返回:

• 如果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

在上面的例子中,sort函数被告知1和2是相同的(并且在1之前将1放在1或2之前无关紧要).这会产生不正确的结果,例如(在Chrome 49中):

[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]