为什么在 Java 1.8 中这样排序

Question

摘自 Java Joshua Bloch 和 Neal Gafter 的益智游戏

import java.util.*;

public class BananaBread {
    public static void main(String[] args) {
        Integer[] array = { 3, 1, 4, 1, 5, 9 };
        Arrays.sort(array, new Comparator<Integer>() {
            public int compare(Integer i1, Integer i2) {
                return i1 < i2 ? -1 : (i2 > i1 ? 1 : 0);
            }
        });
        System.out.println(Arrays.toString(array));
    }
}

预期的行为未定义，文本说它 returns [3, 1, 4, 1, 5, 9]。 Java 1.7 版之前都是如此。但是，在 Java v. 1.8 中，输出是排序后的列表。

我可以看到 Timsort 是 Java 1.8 中的新功能，但我不确定该算法如何在不一致的比较器（例如上面给出的比较器）下运行。任何帮助或深入了解如何做到这一点将不胜感激。

Answer 1

Java 8 使用修改后的合并排序。它使用的关键行是

// From TimSort.binarySort
while (left < right) {
    int mid = (left + right) >>> 1;
    if (c.compare(pivot, a[mid]) < 0)  // compares for less than 0.
        right = mid;
    else
        left = mid + 1;
}

注意：它只关心你是return-1还是0（更具体的是<0，true or false）

您的比较器与

相同

return i1 < i2 ? -1 : 0;

所以在对这段代码重要的所有方面都是正确的。

注意：如果您像这样更改代码

return i1 > i2 ? +1 : 0;

它不对任何东西进行排序。

为什么在 Java 1.8 中这样排序

Why does this sort in Java 1.8

java

arrays

sorting

timsort