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)
我看到了this。但我无法清楚地理解为什么我会得到这个例外。
是否有更好的方法用上面给出的策略对List<CharacterIndex>
进行排序?
将@ RealSkeptic的评论置于答案中:
Comparable
says that:此接口对实现它的每个类的对象强加一个总排序。
要查看有关完全有序集的更多信息,请参阅this链接。
假设我的初始列表是[(d,2), (y,1), (b,1)]
(y,1) < (b,1)
作为相同的指数,我不想洗牌顺序。(b,1) < (d,2)
对于不同的索引,我可以随机播放顺序,然后我只需要比较字符。通过传递性,(y,1) < (d, 2)
。哪个不是真的。
所以这不是一个完全有序的比较。因此它打破了Comparable
界面提供的规则。
因此,对于这种排序策略,我们无法正确实现compareTo
(遵守Comparable
接口的合同)。
您的排序策略应始终定义实现Comparable
的类对象的总排序
这是因为如果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注意到的那样,由于关系不再具有传递性,因此无法将索引考虑在内。