用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 b'/ code>。如MDN（链接）所述，比较函数也可以返回零，以确保两个项目的相对位置保持不变：

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

确实，通过添加返回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标准不保证这种行为，因此并不是所有的浏览器（例如，至少可以追溯到2003年至少
的Mozilla版本）都尊重这一点。

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版本至少可以追溯到
）尊重这一点。

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.

生成有效，可满足的排序（数学上：除法这些项目分为完全订购的等价类），比较必须具备某些属性。它们列在 排序规范中 作为一致比较功能的要求。

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 [...]不是此数组元素的一致比较函数，排序的行为是实现定义的。

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屋！