3

sort我正在使用此 Javascript 代码查看调用该方法时比较数组元素的顺序。

function log(text)
{
    document.documentElement.appendChild(document.createElement('div')).appendChild(document.createTextNode(text));
}

[5, 4, 3, 2, 1].sort(function (a, b) {
    log("comparing " + a + " and " + b);
    return a - b;
});

看到不同的浏览器由于不同的实现而产生不同的输出，我并不感到惊讶。我无法理解的是为什么 IE 和 Opera 有时会连续两次比较同一对值。这对我来说没有任何意义。排序数组看起来像是一个基本的语言功能，我可能在这里遗漏了一些东西。有人可以解释这种行为吗？

这是我的测试结果：

IE 9 和 10

  • 比较 4 和 5
  • 比较 4 和 5
  • 比较 3 和 5
  • 比较 3 和 4
  • 比较 2 和 5
  • 比较 2 和 4
  • 比较 2 和 3
  • 比较 1 和 5
  • 比较 1 和 3
  • 比较 1 和 2

火狐

  • 比较 5 和 4
  • 比较 5 和 3
  • 比较 4 和 3
  • 比较 2 和 1
  • 比较 5 和 1
  • 比较 3 和 1
  • 比较 3 和 2

铬合金

  • 比较 5 和 4
  • 比较 5 和 3
  • 比较 4 和 3
  • 比较 5 和 2
  • 比较 4 和 2
  • 比较 3 和 2
  • 比较 5 和 1
  • 比较 4 和 1
  • 比较 3 和 1
  • 比较 2 和 1

歌剧

  • 比较 5 和 4
  • 比较 2 和 1
  • 比较 3 和 1
  • 比较 3 和 1
  • 比较 3 和 2
  • 比较 5 和 1
  • 比较 4 和 1
  • 比较 4 和 2
  • 比较 4 和 3

以及概念证明：http: //jsfiddle.net/Sd9ph/

4

1 回答 1

2

我们不知道细节，因为它们的实现不是开源的。

然而，Opera 似乎使用了一些合并排序，其中合并阶段包括比较范围边界（在可能的情况下进行更有效的连接而不是逐项合并）。在最小的情况下，其中一个范围中只有一个项目 - 如果它不能只是前置，则将对其进行两次比较。它可以使用优化，但不会经常发生，所以显然不值得。

您可以使用三项数组检查此处的行为。示例[3,2,1]：

3 2 1

[3][2 1] // divide

[3][2 1] // compare (and exchange)
    ^ ^
[3][1 2] // compare upper with lower boundary (would concat if possible)
  ^^
[3][1 2] // but they're overlapping, so let's merge…
 ^  ^
1 [3][2] // …by comparing smallest items from each set
   ^  ^
1 2 3

的示例[2,1,4,3]，具有连接：

2 1 4 3

[2 1][4 3] // divide

[2 1][4 3] // and sort sub-arrays
 ^ ^  ^ ^
[1 2][3 4] // compare boundaries
    ^^
1 2 3 4    // uh, we're done already!

这种连接将使（至少部分）已经排序的数组的合并排序更快。

相比之下，Internet Explorer 执行经典的插入排序。我假设它首先测试数组是否已经排序 - 在第一次比较时失败，4 不是 >= 5。然后它在 5 之前插入 4，在 5 和 4 之前插入 3，在 5 和 4 和 3 之前插入 2，并且由于 1 缺少与 4 的比较，因此它似乎使用了一种二进制搜索。

于 2013-04-23T13:00:09.070 回答