java - 找到比较器可能不起作用的情况

Question

我想对(整数列表)的列表进行排序，以便将包含数字 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)

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

Answer 1

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。除了减少冗长之外，它还使编写正确的 compare 方法变得更加容易。

这是有效的，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))。