java - Collections.sort() 在大型 ArrayList 中失败，经常排序

Question

我看过很多与此问题相关的帖子，但我执行的每一次桌面检查和我实现的建议都没有帮助。我不知道我是如何违反比较者的契约(Contract)的。当然，我不经常使用比较器。

我有一个很大的对象 ArrayList，每次更新时都会对它们进行排序，因为它们的位置经常变化。我必须按照从左下角到右上角的顺序渲染这些对象，以保持类似于 2D 程序的“深度”外观。

这是我的比较器:

@Override
public int compare(RenderObject o1, RenderObject o2) 
{
    //if(o1 == null || o2 == null)
    //    return 0;

    if(o1 == null)
        return -1;
    else if(o2 == null)
        return 1;

    //vertices in order top-left, top-right, bottom-right, bottom-left
    PointF[]    bounds1 = o1.getVertices(),
                bounds2 = o2.getVertices();

    //if(bounds1 == null || bounds2 == null || bounds1.equals(bounds2))
    //  return 0;

    if(bounds1 == null)
        return -1;
    else if(bounds2 == null)
        return 1;

    if(bounds1[0].x >= bounds2[1].x || bounds1[3].y <= bounds2[0].y)
        return 1;
    else if(bounds1[1].x <= bounds2[0].x || bounds1[0].y >= bounds2[3].y)
        return -1;

    return o1.getZOrder() < o2.getZOrder() ? 1 : (o1.getZOrder() > o2.getZOrder() ? -1 : 0);
}

谁能解释一下哪里违反了契约(Contract)。我尝试对 o1 和 o2 使用完全相同的顶点进行桌面检查，但无法弄清楚它们是如何不相等的。如果无济于事，我想我将不得不手动实现排序，这可能会更有效率，因为并非所有对象都会在每次更新时移动，但我仍然想修复此代码，如果没有其他 future 引用的话。

编辑:这是实际的错误，但它是所有其他人因这个问题而停止的地方。

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(Unknown Source)
at java.util.TimSort.mergeAt(Unknown Source)
at java.util.TimSort.mergeForceCollapse(Unknown Source)
at java.util.TimSort.sort(Unknown Source)
at java.util.TimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at java.util.Collections.sort(Unknown Source)
at ....Map.update(Map.java:237)
at ....GameMain.update(GameMain.java:76)
at ....BasicGame.start(BasicGame.java:173)
at ....GameMain.main(GameMain.java:121)

Answer 1

你必须处理null吗？因为那可能是个问题。

现在，当涉及到 null 时，您将返回“equal”。

所以1 < 2，且1 == null，所以null应该小于2，不过这里也是相等的。

要修复它，要么在 null 上出错(如果这是一个选项，您需要避免空值)，或者使 null 最小。

if (a == b) return 0;
if (a == null) return -1;
if (b == null) return 1;

---

此外，如果您执行 >=，则不能返回 1 或 -1。它可能是平等的，对吧？特别是，将对象与自身(或自身的克隆)进行比较必须返回 0。这似乎是单元测试的好案例。