Tag: timsort

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; } }; […]