javascript - 是否有黑盒方法来检测排序算法是否稳定？

Question

在 JavaScript(在其他地方有些适用)中，您不知道您的代码在哪个目标实现上运行，有没有一种方法可以检测底层排序算法(Array.sort )稳定与否，只知道它遵循the specification ？

我可以在 webkit 中找到 2 个测试 (1) (2) ，但这些测试的可靠性如何？ (这个检查可以用 PCP 完成吗？)我正在寻找一个数学上合理的解决方案。

这是一个棘手的问题，因为更高级的排序算法可以根据源数组的长度更改子算法(如 Timsort)。我一直很困惑，因为我运行的每项测试都表明 Google Chrome 浏览器的类型是稳定的，但我看到的所有文档都说它不稳定(the source 会告诉你原因)。

(通常，我使用 this strategy 来使我的排序稳定；它对性能的影响很小但有时很明显)

各种实现中排序的源代码:

• Google Chrome/ium - V8
• Safari - JSC
• Firefox - *Monkey (2) (3)

Answer 1

黑盒测试不能用于确定程序是否满足任何标准，除非您可以测试与标准相关的所有可能输入。黑匣子可以自由地简单地拥有一个将输入映射到输出的查找表(请参阅 Pentium FDIV bug 了解现实世界中的查找表错误)，因此您无法确定您的测试是否排除了其他输入触发违规的可能性。