如果比较函数不可传递,Array.sort()的行为如何？

Question

我正在编写一种算法来对3D盒子进行排序,以便按照从前到后的顺序进行绘制.有一种定义明确,稳定的方法可以决定两个方框中的哪一个位于另一个方框的前面,因此我编写了一个函数来执行该操作,然后我将函数传递Array.prototype.sort()给了正确的绘制顺序.

但是有可能有这样的盒子循环A>B,B>C并且C>A都是真的.这意味着整个列表没有明确定义的排序顺序,即使任何一对的顺序都是明确定义的.

在实践中,这种情况不太可能出现,如果是这样的话,我可以忍受一两个盒子的顺序错误.但在这种情况下,是否存在可以对整个列表进行错误排序或崩溃的JS实现？

---

11月16日更新

只是为了填写更多的上下文,现在项目已经完成(事实上,如果你愿意,没有理由你不能看它):

我问这个问题的原因是,虽然明显的答案是"你不能使用破坏的比较器排序",但仍然......这是一个类似排序的任务,并且尝试进行排序确实会产生一些有用的结果.

在我的具体应用中,上面显示的循环情况从未实际出现过(至少,你必须真正尝试).我希望我可以对对象进行排序,这样,如果删除了属于循环的任何元素,剩下的元素将按严格的顺序排列.但我没有达到这一点,这就是为什么:

我的第一个想法是,当我比较两个盒子时,无论哪个盒子位于X轴前面,或者 Y轴或 Z轴都在前面排序.但这意味着我不是比较框(A),而是真正比较无限的交叉形状(B):

- 这意味着它们像疯了一样重叠,而且循环情况并不罕见; 事实上,如果使用3个或更多个对象,我可能会使用随机顺序.

在某些时候,我看到了这个有用的参考,这表明我应该只测试在屏幕上实际重叠的成对的盒子.添加该测试(并且如果它们不重叠则排序框为"相等")会产生更好的结果,框中的顺序通常不正确,但仍然存在大量错误.

问题是快速排序算法不会测试每一对可能的值(如果他们这样做,它们就是O(n ²)).将A和B排序为"相等"并不仅仅意味着它们的相对顺序并不重要; 这意味着如果C在A之前排序,它也必须在B之前排序.无论浏览器使用什么类型的算法,它都会跳过基于此假设的比较,因此它不会测试我需要它来测试的每对盒子.

最后,我编写了我自己的无用的,天真的排序代码(测试每个框,直到找到重叠).我的屏幕上永远不会有超过40个对象,所以性能还可以,而且结果经常是正确的.一个更彻底的算法将涉及回溯,并会提出停止问题,所以我在这里停止.

所以,这不是最令人满意的结论,但有时它就是如此.希望无论如何,这将为其他人提供一些帮助(或残酷的娱乐).

Answer 1

如果顺序不是传递 \xe2\x80\x93 正如你所说，该类型允许循环关系A > B ; B > C ; C > A\xe2\x80\x93 那么我不知道项目顺序错误意味着什么：- ）

\n\n

ECMAScript（ECMA-262，5.1 版）的标准规定Array.prototype.sort：

\n\n

\n

如果comparefn不是未定义的，并且不是该数组元素的一致比较函数（见下文），则 的行为sort是实现定义的。

\n

\n\n

\xe2\x80\x9c 参见下面的\xe2\x80\x9d 解释说，是的， comparefn需要比较的传递性才能符合 \xe2\x80\x9cconfirm\xe2\x80\x9d 的资格。

\n\n

\n

如果满足以下所有要求，则函数comparefn是一组值的一致比较函数[\xe2\x80\xa6]S

\n\n

\n
• 如果a =CF b和b =CF c，则a =CF c（ 的传递性=CF）
\n
• 如果a < CF b和b <\\ CF c，则a <\\ CF c（ 的传递性<\\ CF）
\n
• 如果a >CF b和b >CF c，则a >CF c（ 的传递性>CF）
\n

\n

\n\n

因此，正如您所描述的，您的非传递比较函数调用规范的 \xe2\x80\x9cimplementation-defined\xe2\x80\x9d 子句。

\n\n

我建议阅读 \xe2\x80\x9cimplementation-defined\xe2\x80\x9d 因为 \xe2\x80\x9c 可以做任何事情或什么都不做，不可预测，并且仍然符合此规范\xe2\x80\x9d。

\n