Array.sort 性能如何受输入的初始排序影响？

Question

输入的顺序是否会影响 Array.sort() 的性能？如果可以，怎么做？

Answer 1

这取决于几件事：

运行时（不同的browsers/runtimes使用不同的排序算法）
您输入的内容相对于所需顺序的排列方式
是否使用自定义比较器（也与上一点有关）

我正在处理的一个应用程序在一个模块中经历了严重的性能下降，该模块在它命中的 API 端点开始按排序顺序提供数据后对 35K+ 字符串列表进行排序。前端排序花费的时间从大约 30 毫秒减少到 6 秒 (200x)。

排序是使用自定义比较器完成的，该比较器优先处理以特定后缀结尾的字符串。如果 none 或两个字符串都以后缀结尾，则使用自然顺序。我使用浏览器开发人员工具分析了模块，发现大部分时间都花在了比较上。该配置文件还显示 QuickSort 是 Array.sort() 使用的基础算法（至少在 Chrome 中）。

这很奇怪，因为 QuickSort 应该不受输入顺序的影响。根据维基百科：

[the worst case] may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations (e.g., the Lomuto partition scheme as described above) when all the elements are equal.

我开始好奇并对进行排序的多种变体进行了基准测试。我在命令行中的节点上使用 benchmark.js 运行。基准测试和浏览器都在 v8 之上运行，因此它们应该使用相同的排序算法。结果令人惊讶：

6 tests completed.

  Ordered array, sorted with a default comparator           x 34.27 ops/sec ±1.07% (59 runs sampled)
  Ordered array, sorted with a custom comparator            x  0.18 ops/sec ±2.81% (5 runs sampled)
  Ordered array, shuffled, sorted with a custom comparator  x 38.37 ops/sec ±3.67% (51 runs sampled)
  Ordered array, shuffled, sorted with a default comparator x 29.20 ops/sec ±1.28% (51 runs sampled)
  Unordered array, sorted with a default comparator         x 28.38 ops/sec ±1.28% (50 runs sampled)
  Unordered array, sorted with a custom comparator          x 42.10 ops/sec ±1.32% (55 runs sampled)

这些结果表明性能下降是因为数据分布与比较器有关。以下是输入的一些特征：

比较器优先考虑的后缀 (/Prod) 匹配大约 20% 的字符串
当字符串按字母顺序排序时，以/Prod结尾的字符串很可能在整个
ABC/Alpha、ABC/Beta、ABC/Prod 等序列很常见。

这可能使算法更有可能select一个在其子序列中处于极端的枢轴，从而导致非常大的数要执行的元素之间的比较。

这只发生在Chrome 61。我已经测试了Firefox 52.3 和Safari 10.1，问题没有重现。我猜这是因为使用了不同的排序算法。

Array.sort 性能如何受输入的初始排序影响？

How is Array.sort performance affected by the initial ordering of the input?

javascript

sorting

quicksort

comparator