JavaScript 中的排序:每个比较函数都应该有一个“返回 0”语句吗?

IT技术 javascript sorting
2021-02-10 15:21:35

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

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

所以它是一个比较函数,如果a大于则返回 1,如果小于 OR EQUAL TOb返回-1 如 MDN ( link ) 所述,比较函数也可以返回零,以确保两个项目的相对位置保持不变: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 版本)都尊重这一点。

指的是行为,这ab如果返回0应保持不变。那么也许,通过返回 0,我们在不同的浏览器中得到一个稍微不同的排序数组?这可能是一个原因吗?还有什么其他好的理由根本不返回零吗?

2个回答

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

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

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

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

指的是行为,如果返回 0,a 和 b 应该保持不变。

a的位置b可能保持不变只是稳定排序的要求这不是一个特定的行为,一些浏览器已经实现了一个不稳定的排序算法。

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

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

最突出的一个是自反性,要求一个项目a等于a(它自己)。另一种说法是:

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

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

规范说

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

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

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

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

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

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

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

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

懒惰并希望数组不包含重复项。

现在规范保证了稳定的排序,但它只在最近的环境中实现。
2021-04-02 15:21:35

比较方法应该遵守约定

Math.sign(compare(a, b)) = -Math.sign(compare(b, a))

如果您在 a==b 时返回非零答案,则违反了该合同。

好的,但是如果我不遵守这一点,会失败吗?在某些情况下算法会崩溃吗?在 MDN 上,它只要求比较函数应该始终为特定的一对项目返回相同的值,这是有保证的,即使我在两个项目相同的情况下返回 -1 也是如此。
2021-03-14 15:21:35
@basilikum:这取决于使用的算法:-) 有关详细信息,请参阅我的答案。
2021-03-19 15:21:35