在JavaScript中sorting:每个比较函数是否应该有一个“返回0”语句?

我最近阅读了许多关于JavaScriptsorting的答案,而且我常常偶然发现一个看起来像这样的比较函数:

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

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

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

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

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

实际上,通过添加return 0语句,sortingalgorithm通常需要更less的迭代,并且运行速度更快( JSPerf )。

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

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

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

参考行为,如果返回0,则ab应该保持不变。 所以也许,通过返回0,我们会在不同的浏览器中得到一个稍微不同的sorting数组? 这可能是一个原因吗? 还有没有其他很好的理由不归零?

2 Solutions collect form web for “在JavaScript中sorting:每个比较函数是否应该有一个“返回0”语句?”

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

less写字母 由于省略了比较,可能会稍快一点。 所有其他的影响是不利的

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

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

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

ab的位置可能保持不变只是稳定sorting的要求。 这不是一个特定的行为,一些浏览器已经实现了一个非稳定的sortingalgorithm。

但是,返回零的实际目的是a不是在b之前sorting(如果小于0),也不是ba之前sorting(如果大于0) – 基本上当a等于b 。 这是比较必须的 ,所有的sortingalgorithm都遵从它。

为了产生有效的,可满足的sorting(math上的:将项目划分为完全sorting的等价类),比较必须具有某些属性。 它们在规范中列出,作为“ 一致比较function ”的要求。

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

compare(a, a)必须始终返回0

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

规范说

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

这基本上意味着:如果您提供了一个无效的比较函数,数组可能不会正确sorting。 它可能会随机置换,或者sort调用甚至可能不会终止。

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

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

那么如果你没有返回0等价物品会发生什么? 有些实现没有任何问题,因为他们从来没有比较一个项目本身(即使在数组中的多个位置),人们可以优化这一点,并省略昂贵的比较函数调用,当它已经知道结果必须为0。

另一个极端将是一个永不终止的循环。 假设你有两个相同的项目,你会比较后者与前者,并意识到你必须交换他们。 再次testing,后者会比前者小,你不得不再次交换。 等等…

但是,一个高效的algorithm大多不会再testing已经比较的项目,所以通常实现将终止。 尽pipe如此,它可能会做多less或多或less的交换,实际上是不必要的,因此花费的时间要长于一致的比较function。

还有没有其他很好的理由不归零?

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

比较法应服从合同

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

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

  • 在Python中使用numpy.linalg.eig后sorting特征值和相关的特征向量
  • 如何通过不同的std :: vector的值对std :: vector进行sorting?
  • 如何sorting在Python中的字母数字集
  • 如何在不同的时间通过不同的参数对列表进行sorting
  • 对自定义class级列表进行sorting<T>
  • 最快的方法来sorting10个数字? (数字是32位)
  • 问题sorting使用成员函数作为比较
  • 混合字数string的人性化或自然数字sorting
  • 有一个倒挂的字符?
  • Underscore:基于多个属性的sortBy()
  • search元素的有效方法