是否有黑盒方法来检测排序算法是否稳定？
在JavaScript中（某种程度上适用于其他地方），您不知道代码在哪个目标上运行，是否有一种方法可以检测底层排序算法（Array.sort）是否稳定，只知道它如下the specification？是否有黑盒方法来检测排序算法是否稳定？
我可以在webkit (1)(2)中找到2个测试，但这些测试有多可靠？ （可以用PCP来完成这项检查吗？）我正在寻找一种数学上可行的解决方案。
这是一个棘手的问题，因为更高级的排序算法可以根据源数组长度（如Timsort）更改子算法。我一直困惑，因为我运行的每个测试都表明谷歌浏览器稳定，但我所见过的所有文档都表示它不稳定（the source会告诉你为什么）。
（通常情况下，我用this strategy让我的各种各样的稳定;它具有体积小，但有时noticable性能的影响）
的源代码在各种实现排序：
运行一个小的内部测试，检查？你可以使用“按排名打牌，然后用*的例子”来检查稳定性。
请参见：https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
我不知道你需要多少卡检查稳定性 - 也许5左右？
数学上的声音，呃？这将要求算法中的每条路径都被证明是稳定的 - 以及它们的每个组合。对于任何可能的数据。
确实存在这样的算法 - 但它们很可能是为了满足这个要求而设计的。所以如果是这样，它可能会说它在某个地方。
至于一个证明类似的测试，这可能属于类似的问题作为一个停机问题。
不确定是否需要调用暂停问题，但应该清楚的是超指数搜索对于给定输入大小涵盖*全部*可能性是必需的 – 2013-05-15 21:04:39
黑箱测试不能被用来确定程序符合任何标准，除非你可以测试相关的标准，所有可能的输入。一个黑匣子可以*地拥有一个将输入映射到输出的查找表（请参阅Pentium FDIV bug以了解真实世界的查找表错误），因此您无法确定您的测试是否排除了某些其他输入触发违规的可能性。
为什么冒这个险？对于大多数合理的数据集，合并排序的JavaScript实现应该足够快。挑选一对夫妇并进行基准测试并使用最好的一个。
你只能在概率上做出这样的决定：例如，我可以定义一个排序算法'S'，输入'I'。通常情况下，'S'将实际的分类工作排除在某种稳定的排序算法'T'上，*但*当'I'等于某个特殊值'I''时，它使用非稳定排序'U'。你永远不会证明'S'是非稳定的，除非你运气好，恰巧通过'I''作为输入。更现实的是，也许'S'使用稳定的排序，除非'I'很长。同样，如果您测试适当长的输入，您只会观察到非稳定排序。 – apsillers 2013-05-15 20:43:42
如果规范说明它不稳定，那并不意味着您可以期望在排序数组时排序项目，而是您不能依赖它;没有承诺。 （当前）实现恰好稳定并不意味着它将永远是或者所有平台上的chrome运行。 – frozenkoi 2013-05-15 20:47:40
我同意@MarZab这是一个暂停问题的问题。如果您将其标记为[计算机科学]和/或[计算机科学理论]，您可能会看到更多的关注。 – apsillers 2013-05-15 20:47:45