在JavaScript中sorting:不应该返回一个布尔值足以比较函数?

我总是这样成功地sorting我的数组(当我不想要标准的字典sorting):

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

现在,有人告诉我这是错误的,而且我需要return ab 。 这是真的,如果是的话,为什么? 我已经testing了我的比较function,它的工作原理! 另外,为什么我的解决scheme在错误的时候如此常见 ?

TL; DR

我总是这样成功地sorting我的数组

不,你没有。 并没有注意到它。 一个快速的反例:

 > [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意味着这两个元素被认为是相等的 – sortingalgorithm认为。

深入的解释

JavaScript中的比较函数

比较function如何工作?

Array::sort方法可以将可选的自定义比较函数作为参数。 该函数需要两个参数(通常称为ab ),它应该比较,并应该返回一个数字

  • a被认为大于b并且应该在它之后sorting时> 0
  • == 0a被认为等于b ,并不重要
  • a被认为小于b并且应该在它之前被sorting时< 0

如果它没有返回一个数字,结果将被转换为一个数字(这对布尔值是很方便的)。 返回的数字不需要是完全-101 (尽pipe通常是)。

一致的sorting

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

 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 

如果这个要求被破坏,那么这个sorting将会performance为未定义的。

sort上引用了ES5.1规范 (在ES6规范中也是这样 ):

如果comparefn不是该数组元素的一致比较函数,则sort的行为是实现定义的。

如果对于集合S中的所有值abc (可能是相同的值)满足以下所有要求,则函数comparefn是一组值S的一致比较函数:符号a <CF b表示comparefn(a,b) < 0 ; a =CF b表示comparefn(a,b) = 0 (任一符号); a >CF b表示comparefn(a,b) > 0

当给定一对特定的ab值作为其两个参数时comparefn(a,b)调用comparefn(a,b)总是返回相同的值v 此外, Type(v)是数字,并且v不是NaN 请注意,这意味着对于给定的ab对来说, a <CF ba =CF ba >CF b中的一个是正确的。

  • 调用comparefn(a,b)不会修改这个对象。
  • a =CF a ( 反身性 )
  • 如果a =CF b ,则b =CF a ( 对称 )
  • 如果a =CF bb =CF c ,则a =CF c=CF 传递性)
  • 如果a <CF bb <CF c ,则a <CF c<CF传递性)
  • 如果a >CF bb >CF c ,则a >CF c>CF传递性)

注:上述条件是必要的和足够的,以确保comparefn将集合S划分为等价类,并且这些等价类是完全有序的。

呃这是什么意思? 我为什么要在乎?

sortingalgorithm需要将数组的项目相互比较。 做一个好的,有效率的工作,不一定需要把每个项目相互比较,但是需要能够推理他们的订货。 要做到这一点,有一些自定义比较function需要遵守的规则。 一个微不足道的是,一个项目a等于自己( compare(a, a) == 0 ) – 这是上面列表中的第一个项目(反思性)。 是的,这是一个math,但支付很好。

最重要的是传递性。 它说,当algorithm比较了两个值ab ,还有bc ,并且通过应用比较函数(例如a = bb < c ,那么可以预期 a < c成立。 这似乎只是合乎逻辑的,并且对于定义明确,一致的sorting是必需的。

但是你的比较函数确实会失败 。 让我们看看这个例子:

  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 

糟糕! 这就是为什么一个sortingalgorithm可能会失败(在规范中,这是“ 依赖于实现的行为 ” – 即不可预知的结果)。

为什么错误的解决scheme如此普遍?

因为在许多其他语言中,有sortingalgorithm不期望三路比较,而只是一个布尔运算符。 C ++ std::sort就是一个很好的例子。 如果需要确定相等性,它将简单地应用两次交换参数。 无可否认,这可以更有效率,更不容易出错,但如果操作员不能内联,则需要更多的调用比较函数。

反例

我已经testing了我的比较function,它的工作原理!

只有运气好,如果你尝试了一些随机的例子。 或者因为你的testing套件有缺陷 – 不正确和/或不完整。

这里是我用来find上述最小反例的小脚本:

 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 ab }).toString() ) // you can also console.log() all of them, but remove the loop! throw a.toString(); }); 

什么比较function是正确的?

当你想要一个词典sorting时,根本不使用比较function。 如果需要,数组中的项目将被串行化。

像关系运算符一样工作的通用比较函数可以实现为

 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) } 

如果你想反向sorting,只要采取适当的一个和b交换。

如果要对复合types(对象等)进行sorting,请使用有问题的属性或方法调用或您想要sorting的任何内容来replace每个a和每个b

sort函数需要一个需要两个参数ab的函数,并返回:

  • 如果a 之前有一个负数b
  • 如果a出现 b 之后,则为正数
  • 如果a和b的相对顺序无关紧要,则为零

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

 ab ret 1 2 -1 3 2 1 2 2 0 

另一方面return a > b产生下面的返回值:

 ab ret implied 1 2 false 0 3 2 true 1 2 2 false 0 

在上面的例子中,sortingfunction被告知1和2是相同的 (并且在1之前的2或2之前放置1并不重要)。 这会产生不正确的结果,例如(在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]