编写 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 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)

我看到了这个。但我无法清楚地理解为什么我会得到这个异常。

有没有更好的方法来List<CharacterIndex>使用上述给定的策略进行排序？

Answer 1

将@RealSkeptic 的评论作为答案：的java-docsComparable说：该接口对实现它的每个类的对象进行了总排序。全排序应遵循以下属性：反身性反对称传递性可比性要了解更多关于完全有序集合的信息，请参见此链接。我的排序策略不是传递的。假设我的初始列表是[(d,2), (y,1), (b,1)](y,1) < (b,1)至于相同的索引，我不想打乱顺序。(b,1) < (d,2)至于不同的索引，我可以打乱顺序，然后我只需要比较字符。通过传递性，(y,1) < (d, 2).&nbsp;这不是真的。所以这不是一个完全有序的比较。因此它打破了Comparable接口提供的规则。所以我们不能对这个排序策略有一个正确的实现compareTo（遵守Comparable接口的约定）。你学到了什么？您的排序策略应始终定义实现的类对象的总排序Comparable

Answer 2

这是因为你有o1.compareTo(o2) == -1 && o2.compareTo(o1) == -1if o1.index == o2.index。方法的约定compareTo是这两个必须是不同的符号：o1.compareTo(o2)和o2.compareTo(o1)。换句话说，这意味着o1小于o2和o2小于o1，这是不可能的。可能的解决方案：@Overridepublic int compareTo(CharacterIndex ci) {&nbsp; &nbsp; return Character.compare(this.c, ci.c);}在这里，我们按其携带的字符进行比较。正如@RealSkeptic 注意到的那样，由于关系不再具有传递性，因此无法考虑索引。