排序多维数组时"Comparison method violates general contract "

Question

我正在使用自定义比较器对二维数组进行排序，在某些情况下会得到以下错误：

java.lang.IollegalArgumentException：比较方法违反了它的一般约定！在第781行，java.base/java.util.TimSort.mergeLo在第518行，java.base/java.util.TimSort.mergeAt在第448行，java.base/java.util.TimSort.mergeCollapse在第245行，java.base/java.util.TimSort.sort在第1442行，java.base/java.util.Arrays.sort

下面是引发此错误的代码：

class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, new SortComparator());
}
}
class SortComparator implements Comparator<int[]> {
public int compare(int []a, int []b) {
if(a[0] < b[0]) {
return -1;
} else if(a[0] > b[0]) {
return 1;
} else {
if(a[1] < b[1]) {
return -1;
} else {
return 1;
}
}
}
}

尽管当我使用以下SortComparator类的实现时，一切都很好：

class SortComparator implements Comparator<int[]> {
public int compare(int []a, int []b) {
if(a[0] < b[0]) {
return -1;
} else if(a[0] > b[0]) {
return 1;
} else {
if(a[1] < b[1]) {
return -1;
} else if(a[1]> b[1]) {
return 1;
} else {
return 0;
}
}
}
}

我能知道SortComparator的第一个实现抛出错误的原因是什么吗？

Answer 1

问题是您的第一个SortComparator实现永远无法返回0。

因此CCD_ 5永远不能返回CCD_；一般合同；用于CCD_ 7实现。

实际上，SortComparator.compare(a, a)将返回1。

---

实际合同在javadoc中。它说的是：

符号sgn(expression)指定¹数学符号函数，该函数被定义为根据表达式的值是负、零还是正返回-1、0或1之一。

实现者必须确保sgn(compare(x, y)) == -sgn(compare(y, x))用于所有x和y。(这意味着compare(x, y)必须抛出异常，当且仅当compare(y, x)抛出异常。(

[…]

当x和y是同一对象时，sgn(compare(x, y)) == -sgn(compare(y, x))为真的唯一方法是如果所有x的-sgn(compare(x, x))为零。

---

^{1-尼特皮克：我认为他们应该用"；表示"；而不是"；表示"；在这里}