TimSort什么时候抱怨破坏的比较器？

Java 7 更改了排序算法 ，使其抛出一个

java.lang.IllegalArgumentException：“比较方法违反了它的一般合同！”

在某些情况下，当使用的比较器出现故障时。 是否可以判断比较器中的哪种错误导致这种情况？ 在我的实验中，如果x！= x无关紧要，如果x <y和y <z但z <x也没关系，但是如果x = y且y = z但是x <z对于某些值确实很重要x，y，z。 这通常是这样吗？

（如果对此有一般规则，可能更容易在比较器中查找错误。但当然最好修复所有错误。:-)）

特别是，以下两个比较器没有让TimSort抱怨：

final Random rnd = new Random(52); Comparator brokenButNoProblem1 = new Comparator() { @Override public int compare(Integer o1, Integer o2) { if (o1  o2) { return Compare.GREATER; } return rnd.nextBoolean() ? Compare.LESSER : Compare.GREATER; } }; Comparator brokenButNoProblem2 = new Comparator() { @Override public int compare(Integer o1, Integer o2) { if (o1 == o2) { return Compare.EQUAL; } return rnd.nextBoolean() ? Compare.LESSER : Compare.GREATER; } }; 

但是下面的比较器确实让它失败了：

  Comparator brokenAndThrowsUp = new Comparator() { @Override public int compare(Integer o1, Integer o2) { if (Math.abs(o1 - o2) < 10) { return Compare.EQUAL; // WRONG and does matter } return Ordering.natural().compare(o1, o2); } }; 

更新：在一些现实生活中，我们遇到了失败，其中没有x，y，z，其中x = y且y = z但x <z。 所以看起来我的猜测是错误的，而且似乎并不是这种特殊的失败。 还有更好的想法？

Answer 1

在查看ComparableTimSort的代码后，我不太确定。 我们来分析吧。 这是抛出它的唯一方法（有一种类似的方法只对交换的角色做同样的事情，因此分析其中一个就足够了）。

 private void mergeLo(int base1, int len1, int base2, int len2) { assert len1 > 0 && len2 > 0 && base1 + len1 == base2; // Copy first run into temp array Object[] a = this.a; // For performance Object[] tmp = ensureCapacity(len1); int cursor1 = tmpBase; // Indexes into tmp array int cursor2 = base2; // Indexes int a int dest = base1; // Indexes int a System.arraycopy(a, base1, tmp, cursor1, len1); // Move first element of second run and deal with degenerate cases a[dest++] = a[cursor2++]; if (--len2 == 0) { System.arraycopy(tmp, cursor1, a, dest, len1); return; } if (len1 == 1) { System.arraycopy(a, cursor2, a, dest, len2); a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge return; } int minGallop = this.minGallop; // Use local variable for performance outer: while (true) { int count1 = 0; // Number of times in a row that first run won int count2 = 0; // Number of times in a row that second run won /* * Do the straightforward thing until (if ever) one run starts * winning consistently. */ // ------------------ USUAL MERGE do { assert len1 > 1 && len2 > 0; if (((Comparable) a[cursor2]).compareTo(tmp[cursor1]) < 0) { a[dest++] = a[cursor2++]; count2++; count1 = 0; if (--len2 == 0) break outer; } else { a[dest++] = tmp[cursor1++]; count1++; count2 = 0; if (--len1 == 1) break outer; } } while ((count1 | count2) < minGallop); // ------------------ GALLOP /* * One run is winning so consistently that galloping may be a * huge win. So try that, and continue galloping until (if ever) * neither run appears to be winning consistently anymore. */ do { assert len1 > 1 && len2 > 0; count1 = gallopRight((Comparable) a[cursor2], tmp, cursor1, len1, 0); if (count1 != 0) { System.arraycopy(tmp, cursor1, a, dest, count1); dest += count1; cursor1 += count1; len1 -= count1; // -->>>>>>>> HERE IS WHERE GALLOPPING TOO FAR WILL TRIGGER THE EXCEPTION if (len1 <= 1) // len1 == 1 || len1 == 0 break outer; } a[dest++] = a[cursor2++]; if (--len2 == 0) break outer; count2 = gallopLeft((Comparable) tmp[cursor1], a, cursor2, len2, 0); if (count2 != 0) { System.arraycopy(a, cursor2, a, dest, count2); dest += count2; cursor2 += count2; len2 -= count2; if (len2 == 0) break outer; } a[dest++] = tmp[cursor1++]; if (--len1 == 1) break outer; minGallop--; } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP); if (minGallop < 0) minGallop = 0; minGallop += 2; // Penalize for leaving gallop mode } // End of "outer" loop this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field if (len1 == 1) { assert len2 > 0; System.arraycopy(a, cursor2, a, dest, len2); a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge } else if (len1 == 0) { throw new IllegalArgumentException( "Comparison method violates its general contract!"); } else { assert len2 == 0; assert len1 > 1; System.arraycopy(tmp, cursor1, a, dest, len1); } } 

该方法执行两个排序运行的合并。 它通常合并，但一旦遇到一方开始“赢”（即总是小于另一方），就会开始“驰骋”。 Gallopping试图通过向前看更多元素而不是一次比较一个元素来加快速度。 由于运行应该排序 ，outlook未来是好的。

您会看到只有当len1在结尾len1为0时才会抛出exception。 第一个观察结果如下：在通常的合并期间， 永远不会抛出exception，因为循环在len 1直接中止。 因此，只能因疾驰而抛出exception 。

这已经强烈暗示exception行为是不可靠的：只要你有小数据集（如此小以至于生成的运行可能永远不会驰骋，因为MIN_GALLOP为7 ）或生成的运行总是巧合地生成一个永不MIN_GALLOP的合并，你永远不会收到例外。 因此，在不进一步检查gallopRight方法的情况下，我们可以得出结论：您不能依赖exception： 无论您的比较器有多么错误，它都可能永远不会抛出。

Answer 2

从文档 ：

IllegalArgumentException – （可选）如果发现数组元素的自然顺序违反了Comparable合同

我在提到的合同上找不到太多，但恕我直言，它应该代表一个总顺序 （即compareTo方法定义的关系必须是传递的 ， 反对称的和总的 ）。 如果不满足该要求， sort可能会抛出IllegalArgumentException 。 （我说可能是因为未能满足这一要求可能会被忽视。）

编辑：添加了使关系成为总订单的属性的链接。