用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
a，b则应保持不变。因此，也许通过返回0，我们在不同的浏览器中得到了稍微不同的排序数组？这可能是原因吗？还有其他根本不归零的良好理由吗？

阅读 294

2020-05-01

共1个答案

一尘不染

所以我想知道省略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。

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

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

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

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

2020-05-01