我最近阅读了许多有关使用JavaScript进行排序的答案,而且我经常偶然发现一个如下所示的compare函数:
array.sort(function(a,b){ a > b ? 1 : -1; });
因此,它是一个比较函数,如果a大于1则返回1,如果小于OR EQUAL TO b则返回-1 。如MDN(link)所述,比较函数也可以返回零,以确保两项的相对位置保持不变:a``b
a
b
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
所以我想知道省略return 0声明是否有任何好处。
我意识到在MDN上,它还说:
注意:ECMAscript标准不保证此行为,因此并非所有浏览器(例如,至少可追溯到2003年的Mozilla版本)都遵守此规定。
指的是该行为,如果返回0 a,b则应保持不变。因此,也许通过返回0,我们在不同的浏览器中得到了稍微不同的排序数组?这可能是原因吗?还有其他根本不归零的良好理由吗?
所以我想知道省略return 0语句是否有任何优势。
少键入字母。由于省略了一个比较,因此可能会快一点。所有其他影响都是 不利的 。
我意识到在MDN上,它还说: 注意:ECMAscript标准不保证此行为,因此并非所有浏览器(例如,至少可追溯到2003年的Mozilla版本)都遵守此规定。 参照行为,如果返回0,则a和b应该保持不变。
参照行为,如果返回0,则a和b应该保持不变。
这位置a并b可以保持不变,只是针对需求排序稳定。这不是指定的行为,某些浏览器已实现了非稳定的排序算法。
但是,返回零的实际目的是既不a进行排序b(如小于0)也不进行b排序a(如大于0)-基本上在aequals时b。这是 进行比较 的 必备条件 ,所有排序算法均应遵守。
为了产生有效的,令人满意的排序(数学上:将项目划分为完全排序的等效类),比较必须具有某些属性。在规范sort中列出了它们,以作为“ 一致比较功能 ”的要求。
sort
最突出的是自反性,要求一项a等于a(本身)。另一种说法是:
compare(a, a) 必须总是回来 0
compare(a, a)
0
当比较函数不满足此要求时(就像您偶然发现的函数那样),会发生什么?
规格说
如果comparefn[…]不是此数组元素的一致比较函数,则行为sort是实现定义的。
comparefn
这基本上意味着:如果提供的比较函数无效,则数组可能无法正确排序。它可能会随机排列,或者sort调用甚至可能不会终止。
因此,也许通过返回0,我们在不同的浏览器中得到了稍微不同的排序数组?这可能是原因吗?
不,通过返回0,您将在浏览器中获得 正确排序的 数组(由于排序不稳定,可能会有所不同)。原因是,如果不返回0,您将获得稍微不同的置换数组(如果有的话),甚至可能会产生预期的结果,但通常采用更复杂的方式。
那么,如果您不为相等的项目返回0,会发生什么?一些实现对此没有问题,因为它们从不将一个项目与其自身进行比较(即使在数组中的多个位置上都是明显的)-可以优化这一点,并且在已知结果必须为0。
另一个极端是永无止境的循环。假设彼此之间有两个相等的项目,则可以将后者与前者进行比较,并意识到您必须交换它们。再次测试,后者仍然比前者小,您必须再次交换它们。等等…
但是,高效的算法通常 不会 再次 测试已比较的项目,因此通常实现会终止。尽管如此,它可能会进行实际上不必要的或多或少的交换,因此比使用一致的比较功能所花费的时间更长。
还有其他根本不归零的良好理由吗?
懒惰并希望该数组不包含重复项。