JavaScript 中的排序:每个比较函数都应该有一个“返回 0"吗?陈述? [英] Sorting in JavaScript: Should every compare function have a "return 0" statement?

问题描述

我最近阅读了很多关于 JavaScript 排序的答案，我经常偶然发现一个看起来像这样的比较函数:

I recently read many answers about sorting in JavaScript and I often stumble upon a compare function that looks like this:

array.sort(function(a,b){ a > b ? 1 : -1; });

所以它是一个比较函数，如果 a 大于 b 则返回 1，如果 a 小于 OR EQUAL TO 则返回 -1b.如 MDN 所述(link)，比较函数也可以返回零，保证两个项的相对位置不变:

So it is a compare function that returns 1 if a is greater than b and -1 if a is less than OR EQUAL TO b. As described on MDN (link), a compare function can also return zero, to ensure that the relative position of two items remains unchanged:

如果 compareFunction(a, b) 返回 0，保持 a 和 b 不变相互尊重，但对所有不同的人进行排序元素.

If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements.

所以官方的例子看起来更像这样:

So the official examples look more like this:

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

事实上，通过添加 return 0 语句，排序算法通常需要更少的迭代并且总体上运行得更快(JSPerf).

And indeed, by adding a return 0 statement, the sorting algorithm often needs less iterations and runs faster in total (JSPerf).

所以我想知道省略 return 0 语句是否有任何优势.

So I was wondering if there is any advantage on omitting a return 0 statement.

我意识到在 MDN 上，它还说:

I realized that on MDN, it also says:

注意:ECMAscript 标准不保证这种行为，并且因此并不是所有的浏览器(例如 Mozilla 版本至少可以追溯到2003)尊重这一点.

Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.

参考行为，如果返回 0，a 和 b 应该保持不变.那么也许，通过返回 0，我们在不同的浏览器中得到一个稍微不同的排序数组?这可能是一个原因吗?还有什么其他完全不返回零的充分理由吗?

referring to the behavior, that a and b should remain unchanged if 0 is returned. So maybe, by returning 0, we get a slightly different sorted array in different browsers? Could that be a reason? And are there any other good reasons for not returning zero at all?

推荐答案

所以我想知道省略 return 0 语句是否有任何优势.

So I was wondering if there is any advantage on omitting a return 0 statement.

要输入的字母更少.由于省略了比较，它可能会快一点.所有其他影响都是缺点.

Less letters to type. And it might be a tiny bit faster due to the one omitted comparison. All other effects are disadvantages.

我意识到在 MDN 上，它还说:

I realized that on MDN, it also says:

注意:ECMAscript 标准不保证这种行为，并且因此并不是所有的浏览器(例如 Mozilla 版本至少可以追溯到2003)尊重这一点.

Note: the ECMAscript standard does not guarantee this behaviour, and thus not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.

指的是行为，如果 0，a 和 b 应该保持不变被退回.

referring to the behavior, that a and b should remain unchanged if 0 is returned.

a 和 b 的位置可以保持不变只是稳定排序.这不是一个特定的行为，一些浏览器已经实现了一个不稳定的排序算法.

That the position of a and b may remain unchanged is only the requirement for a stable sort. This is not a specified behaviour, and some browsers have implemented a non-stable sort algorithm.

然而，返回零的实际目的是 a 既不在 b 之前排序(好像小于 0)，也不是 b在 a 之前排序(好像大于 0) - 基本上当 a 等于 b 时.这是比较必备的，所有排序算法都遵守它.

However, the actual purpose of returning zero is that neither a is sorted before b (as if less than 0) nor that b is sorted before a (as if greater than 0) - basically when a equals b. This is a must-have for a comparison, and all sorting algorithms obey it.

产生有效的、可满足的排序(数学上:将项目划分为完全有序等价类)，比较必须具有某些属性.它们列在 sort 作为一致的比较函数"的要求.

To produce a valid, satisfiable ordering (mathematically: divide the items into totally ordered equivalence classes), a comparison must have certain properties. They are listed in the spec for sort as requirements for a "consistent comparison function".

最突出的是自反性，要求项 a 等于 a(本身).另一种说法是:

The most prominent one is reflexivity, demanding that an item a is equal to a (itself). Another way to say this is:

compare(a, a) 必须总是返回 0

compare(a, a) must always return 0

当比较函数不满足这一点时会发生什么(就像你偶然发现的那个显然满足)?

What happens when a comparison function does not satisfy this (like the one you stumbled upon obviously does)?

规范说

如果 comparefn […] 不是该数组元素的一致比较函数，则 sort 的行为是实现定义的.

If comparefn […] is not a consistent comparison function for the elements of this array, the behaviour of sort is implementation-defined.

这基本上意味着:如果您提供无效的比较函数，则数组可能无法正确排序.它可能会随机排列，或者 sort 调用甚至可能不会终止.

which basically means: If you provide an invalid comparison function, the array will probably not be sorted correctly. It might get randomly permuted, or the sort call might not even terminate.

所以也许，通过返回 0，我们会得到一个稍微不同的不同浏览器中的排序数组?这可能是一个原因吗?

So maybe, by returning 0, we get a slightly different sorted array in different browsers? Could that be a reason?

不，通过返回 0，您将获得一个正确排序的 跨浏览器数组(由于排序不稳定，这可能会有所不同).原因是不返回 0 会得到稍微不同的排列数组(如果有的话)，甚至可能产生预期的结果，但通常以更复杂的方式.

No, by returning 0 you get a correctly sorted array across browsers (which might be different due to the unstable sort). The reason is that by not returning 0 you get slightly different permuted arrays (if at all), maybe even producing the expected result but usually in a more complicated manner.

那么如果您不为等效项返回 0 会发生什么?一些实现对此没有问题，因为它们从不将项目与其自身进行比较(即使在数组中的多个位置很明显) - 可以优化这一点，并在已知结果必须时省略对比较函数的昂贵调用为 0.

So what could happen if you don't return 0 for equivalent items? Some implementations have no problems with this, as they never compare an item to itself (even if apparent at multiple positions in the array) - one can optimise this and omit the costly call to the compare function when it is already known that the result must be 0.

另一个极端是永不终止的循环.假设您有两个相同的项目，您会将后者与前者进行比较，并意识到您必须交换它们.再次测试，后者仍然比前者小，您必须再次交换它们.等等……

The other extreme would be a never-terminating loop. Assuming you had two equivalent items after each other, you would compare the latter with the former and realise that you had to swap them. Testing again, the latter would still be smaller than the former and you'd have to swap them again. And so on…

然而，一个有效的算法大多不会测试已经比较过的项目再次，因此通常实现会终止.尽管如此，它可能会或多或少地进行实际上不必要的交换，因此比使用一致的比较函数需要更长的时间.

However, an efficient algorithm mostly does not test already compared items again, and so usually the implementation will terminate. Still, it might do more or less swaps that actually had been unnecessary, and will therefore take longer than with a consistent comparison function.

还有什么其他充分的理由完全不返回零吗?

And are there any other good reasons for not returning zero at all?

懒惰，希望数组不包含重复项.

Being lazy and hoping that the array does not contain duplicates.

这篇关于JavaScript 中的排序:每个比较函数都应该有一个“返回 0"吗?陈述?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！