java - 编写compareTo的正确实现

Question

private static class CharacterIndex implements Comparable<CharacterIndex> {
    private final char c;
    private final int index;

    public CharacterIndex(char c, int index) {
        this.c = c;
        this.index = index;
    }
}

现在我想覆盖 compareTo此类的方法，如果我有以下 List的CharacterIndex的对象 [('y', 1), ('x', 2), ('b', 3), ('a', 3)]那么排序后，对象应该像 [('b', 3), ('a', 3), ('x', 2), ('y', 1)] .

排序策略:

索引不同的对象可以被打乱(并且应该仅根据字符的值排序)。具有相同索引的对象在排序后应保持其相对顺序。

再举一个例子:

对于[('y', 1), ('w', 2), ('x', 3)]排序后的列表应该是 [(w, 2), (x, 3), (y, 1)]而不是[(x, 3), (w, 2), (y, 1)] .

我的尝试:

@Override
public int compareTo(CharacterIndex ci) {
    if (this.index == ci.index)
        return -1; // don't swap if the index is same
    return Character.compare(this.c, ci.c);
}

但是这种方法给了我一个异常(exception):

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
    at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
    at java.util.Arrays.sort(Arrays.java:1312)
    at java.util.Arrays.sort(Arrays.java:1506)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:141)

我看到了this 。但我无法清楚地理解为什么会出现此异常。

是否有更好的方法对 List<CharacterIndex> 进行排序使用上面给出的策略？

Answer 1

将@RealSkeptic 的评论放入答案中:

java-docs的Comparable说:

This interface imposes a total ordering on the objects of each class that implements it.

总排序应遵循以下属性:

• 自反性
• 反对称性
• 传递性
• 可比性

要了解有关全序集的更多信息，请参阅 this链接。

我的排序策略不具有传递性。

假设我的初始列表是 [(d,2), (y,1), (b,1)]

• (y,1) < (b,1)对于相同的索引，我不想打乱顺序。
• (b,1) < (d,2)对于不同的索引，我可以打乱顺序，然后只需要比较字符。

根据传递性，(y,1) < (d, 2) 。这不是真的。

所以这不是一个完全有序的比较。因此它打破了 Comparable 提供的规则界面。

所以我们无法正确实现 compareTo (遵守 Comparable 接口(interface)的约定)此排序策略。

你学到了什么？

您的排序策略应始终在实现 Comparable 的类的对象上定义总排序。