用JavaScript排序:每个比较函数都应该有一个"返回0"语句吗？

Question

我最近阅读了很多关于JavaScript排序的答案,我经常偶然发现一个比较函数,如下所示:

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

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

如果compareFunction(a,b)返回0,则保持a和b相对于彼此保持不变,但是对于所有不同的元素进行排序.

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

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

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

所以我想知道在省略return 0声明方面是否有任何优势.

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

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

指的是行为,这a和b如果返回0应保持不变.那么也许,通过返回0,我们在不同的浏览器中得到一个稍微不同的排序数组？这可能是个原因吗？是否有任何其他充分理由不返回零？

Answer 1

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

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

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

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

参考行为,如果返回0,则a和b应保持不变.

位置a和b可能保持不变只是稳定排序的要求.这不是指定的行为,并且某些浏览器实现了非稳定的排序算法.

但是,返回零的实际目的是既不a在之前排序b(如果小于0)也不b在之前排序a(如果大于0) - 基本上当a等于时b.这是比较的必备条件,所有排序算法都遵循它.

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

最突出的是反身性,要求物品a等于a(本身).另一种说法是:

compare(a, a) 必须永远回归 0

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

规范说

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

这基本上意味着:如果提供无效的比较函数,则数组可能无法正确排序.它可能会被随机置换,或者sort呼叫甚至可能无法终止.

那么也许,通过返回0,我们在不同的浏览器中得到一个稍微不同的排序数组？这可能是个原因吗？

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

那么如果你没有为同等物品返回0会怎么样？有些实现没有问题,因为它们从不将项目与自身进行比较(即使在数组中的多个位置显而易见) - 可以优化这一点并省略对比较函数的代价高昂的调用,因为已知结果必须是0.

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

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

是否有任何其他充分理由不返回零？

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