java - 如何按Java中的多级字段对arraylist进行排序

Question

Class Activity{
    private int level;
    private Activity predecessor;
}

我的程序创建了 Activity 的实例，将它们放在一个 Arraylist 中，并按 level 和 predecessor 这两个字段对它们进行排序。首先比较前任。

例如，如果predecessor 不是null，则当前 Activity 的前导Activity 应该是第一个，它将是第二个。在满足 predecessor 条件后，可以按 level 对以下内容进行排序。

List<Activity> activities = new ArrayList<Activity>();
//Add some activities.
activities.add(Activity);
activities.add(Activity);
Collections.sort(activities,getActivityComparator());

private Comparator<Activity> getActivityComparator() {
    return new Comparator<Activity>() { 
        public int compare(Activity act1, Activity act2) {                
            if (act1 == null) {
                if (act2 == null) {
                    return 0; // Both activities are null
                } else {
                    return -1; // act1 is NULL, so put act1 in the end of
                    // the sorted list
                }
            } else {
                if (act2 == null) {
                    return 1; 
                }
            }

         Activity preAct2 = act2.getPredecessor();
         if(preAct2!=null&&preAct2==act1)
             return -1;

          //Adding this by Joeri Hendrickx's suggestion
         Activity preAct1 = act1.getPredecessor();
         if(preAct1!=null&&preAct1==act2)
             return 1;

         return act2.getLevel()-act1.getLevel(); 
        }
    };
}

我已经编写了上面的代码并进行了很多测试，但是如果我将不同的排序放入 Arrarylist 中，它会输出不稳定的排序。所以这绝对是不正确的实现方法。似乎根本原因不是每两个元素都进行了比较。说Activity act1>Activity act2(by level condition)，Activity act2>Activity act3(by level condition)，不是说Activity act1>Activity act3(by predecessor condition)。

这里我想到了一个新的思路，就是用冒泡排序代替Collections的接口(interface)排序。它将比较每两个不再需要比较器传递的元素。你怎么看？

谁能帮帮我？

Answer 1

问题是您的比较器没有描述正确的对称和传递关系。

考虑以下三个对象:

act1{predecessor:null, level:1}    
act2{predecessor:act1, level:1}    
act3{predecessor:null, level:0}
act4{predecessor:act2, level:2}

现在，comp 是您的比较器，comp(act1, act2) 将返回 -1，但 comp(act2, act1) 将返回 0。这不是对称。

comp(act1, act2) 将返回 -1，comp(act2, act4) 将返回 -1，但是 comp(act1, act4) 将返回 1。这不是可传递的。

比较器必须描述正确的自反、对称 和传递 关系才能工作。

在看到 Axtaxt 的帖子后编辑:您在此处描述的问题无法通过普通排序来解决，因为根据这些规则，您总是可以构建一个场景，在该场景中，您会在排序层次结构中出现循环。所以不可能仅使用这些数据来制作传递比较器。