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

Question

我已经看过很多与这个问题有关的帖子,但是我执行的所有桌面检查以及我实施的建议都没有帮助.我无法弄清楚我是如何违反比较国的合同的.当然,我不经常使用比较器.

我有一个大型的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);
}

有人可以解释合同违反的地方.我尝试使用o1和o2的相同精确顶点进行桌面检查,但无法弄清楚它们是如何不相等的.如果它无法帮助我想我将不得不手动实现排序,它可能会更有效,因为不是所有对象都会移动每次更新,但我仍然想修复此代码,如果没有其他未来参考.

编辑:这是实际的错误,但它是正确的所有其他人停止这个问题.

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涉及到时,你返回"相等" .

所以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.这似乎是单元测试的一个好例子.