该算法在Stream接口中使用排序方法

Question

当我打印排序方法中的值时，

Stream.of("d", "a", "b", "e", "c", "f")
    .sorted((s1, s2) -> {
        System.out.printf("sort: %s - %sn", s1, s2);
        return s1.compareTo(s2);
    }).forEach(System.out::println);

输出如下:

sort: a - d
sort: b - a
sort: b - d
sort: b - a
sort: e - b
sort: e - d
sort: c - d
sort: c - b
sort: f - c
sort: f - e
a
b
c
d
e
f

我无法理解这里排序算法的逻辑。

Answer 1

下面的答案与OpenJDK(对照10.0.1)有关。

流将排序操作委托给相关的Arrays.sort方法(参见各种SortingOps的end方法)。

对象的排序流

对于排序对象，TimSort(基本上是一种归并排序，当输入的除数足够小时使用插入排序)是首选方法。

作者认为Tim Peter在Python中实现列表排序是一种灵感，并进一步将其归因于论文"Optimistic Sorting and Information Theoretic Complexity", Peter McIlroy, SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), 467-474, Austin, Texas, 25-27 January 1993。

然而，用户也可以请求MergeSort(当数组足够小时回落到插入排序-在OpenJDK 10中它是32或更少的元素)通过设置java.util.Arrays.useLegacyMergeSort属性为true来使用。计划在以后的版本中删除。

原语的排序流

对于原语(byte, char, short, int, long, float, double)的排序流，实现双枢轴快速排序。作者(Vladimir Yaroslavskiy, Jon Bentley和Josh Bloch)没有提供更多关于灵感来源的信息。

<标题> 来源

了解更多信息，请参见OpenJDK代码:

• SortedOps.java -实现相关的流

• Arrays.java - Arrays helper的实现，参见不同的sort方法

• TimSort.java - TimSort的实现

• ComparableTimSort.java -实现Comparable的类的变化

• DualPivotQuicksort.java -基元排序的实现