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

Question

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

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

这是一个棘手的问题，因为更高级的排序算法可以根据源数组的长度（如 Timsort）更改子算法。我一直很困惑，因为我运行的每个测试都显示谷歌浏览器的排序是稳定的，但我看到的所有文档都说它不稳定（来源会告诉你原因）。

（通常，我使用这种策略来使我的排序稳定；它对性能的影响很小但有时很明显）

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

score 5 · Accepted Answer

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

score 1 · Accepted Answer

数学上的声音，嗯？这将要求算法中的每条路径都被证明是稳定的——以及它们的每一种组合。对于任何可能的数据。

确实存在这样的算法——但它们很可能是为了满足这一要求而设计的。因此，如果是，它可能会说它在某个地方。

至于证明类似情况的测试，这可能属于与停止问题类似的问题。

score 1 · Accepted Answer

为什么要冒险？对于大多数合理的数据集，合并排序的 javascript 实现应该足够快。挑选一对并对其进行基准测试并使用最好的。

score 0 · Accepted Answer

运行一个小型内部测试，检查？您可以使用 Wikipedia 中的“按等级，然后按花色的扑克牌”示例来检查稳定性。

我不知道你需要多少张卡来检查稳定性——也许是 5 张左右？

4 回答 4