编写 compareTo 的正确实现

Writing a proper implementation of compareTo 

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;
    }
}

现在我想覆盖此 class 的 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)

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

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

这是因为你有 o1.compareTo(o2) == -1 && o2.compareTo(o1) == -1 如果 o1.index == o2.index。 compareTo 方法的约定是这两个必须具有不同的符号：o1.compareTo(o2) 和 o2.compareTo(o1)。

也就是说，o1小于o2，o2小于o1，这是不可能的。

可能的解决方案：

@Override
public int compareTo(CharacterIndex ci) {
    return Character.compare(this.c, ci.c);
}

这里我们是按它所带的字符来比较的。正如@RealSkeptic 所注意到的，由于关系不再具有传递性，因此无法考虑索引。

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

Comparable 的 java-docs 表示：

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

总排序应遵循以下属性：

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

要了解更多关于什么是完全有序集，请参阅 this link。

我的排序策略是不可传递的。

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

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

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

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

因此我们无法为该排序策略正确实现 compareTo（遵守 Comparable 接口的约定）。

你学到了什么？

您的排序策略应始终定义实现 Comparable

的 class 对象的总排序