我想对List of(整数列表)进行排序,以便将包含数字3的列表放在列表的顶部,使剩余元素的现有顺序保持不变.

    final ArrayList<ArrayList<Integer>> arrayLists = Lists.newArrayList(
        Lists.newArrayList(1, 2),
        Lists.newArrayList(1, 2, 3),
        Lists.newArrayList(1, 2),
        Lists.newArrayList(1, 3),
        Lists.newArrayList(1, 4),
        Lists.newArrayList(1, 2, 3)
    );
    System.out.println(arrayLists);

是的

[[1, 2], [1, 2, 3], [1, 2], [1, 3], [1, 4], [1, 2, 3]]

最初的尝试是在比较器下面

Comparator<List<Integer>> c = new Comparator<List<Integer>>() {
    @Override
    public int compare(final List<Integer> o1, final List<Integer> o2) {
        System.out.println("Compare " + o1 + "<=>" + o2);
        if (o1.contains(3))
            return -1;
        return 0;
    }
};

Collections.sort(arrayLists, c);
System.out.println(arrayLists);

回报

Compare [1, 2, 3]<=>[1, 2]
Compare [1, 2]<=>[1, 2, 3]
Compare [1, 2]<=>[1, 2]
Compare [1, 3]<=>[1, 2]
Compare [1, 3]<=>[1, 2, 3]
Compare [1, 4]<=>[1, 2]
Compare [1, 4]<=>[1, 2]
Compare [1, 2, 3]<=>[1, 2]
Compare [1, 2, 3]<=>[1, 2, 3]
Compare [1, 2, 3]<=>[1, 3]

[[1, 2, 3], [1, 3], [1, 2, 3], [1, 2], [1, 2], [1, 4]]

这是预期的(所有包含3的列表都在顶部)

然而,深入了解javadoc for Comparator表明了这一点

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0.

Finally, the implementor must ensure that compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z

上述比较器没有完全实现,可以通过下面的测试轻松断言.

    final ArrayList<Integer> x = Lists.newArrayList(1, 2, 3);
    final ArrayList<Integer> y = Lists.newArrayList(1, 2);
    System.out.println(c.compare(x,y));
    System.out.println(c.compare(y,x));


Compare [1, 2, 3]<=>[1, 2] => -1
Compare [1, 2]<=>[1, 2, 3] => 0 which is not -(-1)

有没有办法真正证明上面的比较器不适用于某些特定的示例List(它没有将包含3的列表放在顶部)？

解决方法:

Is there any way to prove that above comparator does not work in some cases?

是.最明显的原因是它可以返回-1但从不是正数.这显然违反了第一条规则.

不违反规则的比较器是

Comparator<List<Integer>> c = new Comparator<List<Integer>>() {
    @Override
    public int compare(final List<Integer> o1, final List<Integer> o2) {
        return Integer.compare(o1.contains(3) ? 0 : 1, o2.contains(3) ? 0 : 1);
    }
};

在Java 8中,您可以将其简化为

Comparator<List<Integer>> c = Comparator.comparingInt(o -> o.contains(3) ? 0 : 1);

我建议使用新方法Comparator.comparingX.除了减少冗长之外,它还使编写正确的比较方法变得更加容易.

这有效,Collections.sort的文档保证了这一点

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

另一种方法是迭代原始列表并形成两个单独的列表,一个包含包含3的列表,另一个包含不包含3的列表,然后在末尾使用addAll.这比使用sort(O(n)而不是O(n log n))的方法具有更好的时间复杂度.