排序多维数组时“比较方法违反常规约定”

Question

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

java.lang.IllegalArgument异常：比较方法违反其一般契约！在行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;
            }
        }
    }
}

我能知道第一次实现< code>SortComparator时抛出错误的原因吗？

Answer 1

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

因此＜code＞SortComparator。compare（a，a）永远不能返回0，因为它是 实现的“通用合同”所要求的。

事实上，＜code＞SortComparator。compare（a，a）将返回1。

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

符号sgn（表达式）指定¹数学符号函数，根据表达式的值是负的、零的还是正的，它被定义为返回-1、0或1中的一个。

实现者必须确保所有 x 和 y 的 sgn（compare（x， y）） == -sgn（compare（y， x））。 （这意味着 compare（x， y） 必须抛出异常当且仅当 compare（y， x） 抛出异常。

[...]

当 x 和 y 是同一个对象时，sgn（compare（x， y）） == -sgn（compare（y， x）） 为真的唯一方法是，如果 -sgn（compare（x， x）） 对于所有 x 都是零。

^{1 - 吹毛求疵：我认为他们应该在这里使用“表示”而不是“指定”这个词。}