java - 哪种算法在 Stream 接口(interface)中使用 sorted 方法

Question

关闭。这个问题需要debugging details .它目前不接受答案。












想改进这个问题？将问题更新为 on-topic对于堆栈溢出。

5年前关闭。




Improve this question




当我在 sorted 方法中打印值时，

Stream.of("d", "a", "b", "e", "c", "f")
    .sorted((s1, s2) -> {
        System.out.printf("sort: %s - %s\n", 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 检查)。

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

对对象流进行排序

对于排序对象，TimSort (基本上，当输入的分割足够小时，使用插入排序的合并排序)是首选方法。

作者信用 Tim Peter's implementation of list sort in Python as an inspiration ，进一步将这个想法归因于论文 "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 来使用属性(property)给 true .这计划在 future 的版本中被删除。

对基元流进行排序

对于原语流排序( 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 - 实现基元排序