java - “比较法违反了它的总契约！” - 寻找小样本数据集

Answer 1

这意味着您的 Comparator 存在这样的错误compareTo(a, b) != -compareTo(b, a)

Answer 2

恕我直言，这闻起来更像是排序算法中的错误，而不是我们的比较器中的错误。

对我来说，这听起来像是根据输入集的大小使用了 2 种不同的排序算法。

虽然排序实现中存在错误并非不可能，但问题出在您的 Comparator 中的可能性要大得多......就像异常消息所说的那样。建议您将精力集中在代码上，而不是在库代码中寻找（可能不存在的）错误。

Answer 3

正如 Stephen C 已经猜到的那样，这是使用两种不同排序方法的结果。

看代码java.util.TimSort：

static <T> void sort(T[] a, Comparator<? super T> c) {
    sort(a, 0, a.length, c);
}

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {

    // ...

    // If array is small, do a "mini-TimSort" with no merges
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
        binarySort(a, lo, hi, lo + initRunLen, c);
        return;
    }

    // ...

MIN_MERGE 的值确实是 32，而抛出异常的方法只在其他情况下调用。

Answer 4

错误在我们的比较器中（它违反了 A < B && B < C -> A < C），但我认为 TimSort总是会导致堆栈跟踪似乎是错误的。