Javascript -绕过排序尝试产生奇怪的行为

Question

故事

我正在使用的选择库，这是相当伟大的，除了一个小的事情-它试图排序所有的选项时，它是给定的选择标签。它接受两个字段来控制排序sortFields和sortFilter。从源代码来看，似乎第一个选项只用于搜索(我不使用)，所以我留下了第二个选项，在库构建其模板之前传递给Array的sort函数。我认为给它function() { return 0 }应该做到这一点(因为它将所有元素视为平等，因此不会重新排序数组)，但显然情况并非如此。

当给定constantly 0函数时，sort方法的行为似乎非常奇怪。例子:

Chrome (Linux + Chrome 52.0.2743.82(64位)):

compare = function() {return 0};
[50,100,150,200,250,300,350,400,450,500].sort(compare)
> [50,100,150,200,250,300,350,400,450,500] // All fine up to 10 elements
[50,100,150,200,250,300,350,400,450,500,550].sort(compare)
> [300, 50, 150, 200, 250, 100, 350, 400, 450, 500, 550] // Can't even say what sort of order this is

在Firefox上一切正常。

这是一个Chrome bug吗?是否有其他更好的方法来禁用仅使用排序功能的排序?

(是的，我目前正在为库的补丁禁用它没有黑客。问题具有纯粹的"学术"地位)

Answer 1

如果.sort()比较器返回0，则排序函数可能会对元素重新排序。JavaScript .sort()机制不能保证是稳定的，而一个不稳定的排序恰恰可以做你所观察到的事情。

一个稳定的排序是不重新排序在进程开始时已经有序的元素。

可以这样考虑:当比较器返回0时，排序机制将其解释为"这两个元素具有相同的排序顺序，因此它们的排序顺序无关紧要"。

并不是所有的JavaScript运行时系统都使用相同的排序，所以这就是为什么不同平台的结果会有所不同。

Answer 2

您可以在这里查看https://bugs.chromium.org/p/v8/issues/detail?id=90

条目长度> 10是已知的问题，因为排序算法不同。

Answer 3

Chrome的V8 JS引擎切换到插入排序而不是快速排序短数组:

  // Insertion sort is faster for short arrays.
  if (to - from <= 10) {
    InsertionSort(a, from, to);
    return;
  }

https://github.com/v8/v8/blob/30f8d3354334e7424324429d4e525a3b67b2b8bd/src/js/array.js L809

要获得始终稳定的排序，必须使用另一种稳定的排序函数，例如Underscore的sortBy。