小编典典

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

javascript

我最近阅读了许多有关使用JavaScript进行排序的答案,而且我经常偶然发现一个如下所示的compare函数:

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

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

如果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版本)都遵守此规定。

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


阅读 343

收藏
2020-05-01

共1个答案

小编典典

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

少键入字母。由于省略了一个比较,因此可能会快一点。所有其他影响都是 不利的

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

注意:ECMAscript标准不保证此行为,因此并非所有浏览器(例如,至少可追溯到2003年的Mozilla版本)都遵守此规定。

参照行为,如果返回0,则a和b应该保持不变。

这位置ab可以保持不变,只是针对需求排序稳定。这不是指定的行为,某些浏览器已实现了非稳定的排序算法。

但是,返回零的实际目的是既不a进行排序b(如小于0)也不进行b排序a(如大于0)-基本上在aequals时b。这是 进行比较
必备条件 ,所有排序算法均应遵守。

为了产生有效的,令人满意的排序(数学上:将项目划分为完全排序的等效类),比较必须具有某些属性。在规范sort中列出了它们,作为“ 一致比较功能 ”的要求。

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

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

当比较函数不满足此要求时(就像您偶然发现的函数那样),会发生什么?

规格说

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

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

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

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

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

另一个极端是永无止境的循环。假设彼此之间有两个相等的项目,则可以将后者与前者进行比较,并意识到您必须交换它们。再次测试,后者仍然比前者小,您必须再次交换它们。等等…

但是,高效的算法通常 不会 再次
测试已比较的项目,因此通常实现会终止。尽管如此,它可能会进行实际上不必要的或多或少的交换,因此比使用一致的比较功能所花费的时间更长。

还有其他根本不归零的良好理由吗?

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

2020-05-01