java - TimSort 违规

Question

这个比较器方法有什么问题？

我已阅读: Java error: Comparison method violates its general contract

并理解，如果 c1 > c2，且 c2 > c3，则 c1 > c3。我相信上面的内容应该是正确的。

getMaxCosine() 返回 0..1 之间的值，第二次排序是按照卡片中文本的长度排序，越长排名越高。

public int compare(Card c1, Card c2) {
   if (getMaxCosine(c1) > getMaxCosine(c2)) {
       return -1;
   } else if (getMaxCosine(c1) == getMaxCosine(c2)) {
       return getMatchingText(c1).length() >= getMatchingText(c2).length() ? -1 : 1;
   } else {
       return 1;
   }
}

Answer 1

我认为您的问题出在您的 if-else block 中:

else if (getMaxCosine(c1) == getMaxCosine(c2)) {
       return getMatchingText(c1).length() >= getMatchingText(c2).length() ? -1  : 1;
}

如果 getMatchingText(c1).length() 等于 getMatchingText(c2).length() 则返回 -1。这会产生“不稳定”的排序:换句话说，两个具有相同值的对象在排序后顺序将颠倒。此外，对于在此比较器下相等的 Card，您应该返回 0。我建议将 >= 比较更改为 if-else block 中的 >:

else if (getMaxCosine(c1) == getMaxCosine(c2)) {
       if (getMatchingText(c1).length() == getMatchingText(c2).length()) return 0;
       return getMatchingText(c1).length() > getMatchingText(c2).length() ? -1  : 1;
}