Stream接口中使用了哪些排序算法？

Question

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

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

我不理解这里排序算法的逻辑。如有帮助，将不胜感激。

- Ad Infinitum

---

嗯，有趣的是它两次比较了 b - a。 - eckes

Answer 1

以下答案与OpenJDK相关（经过对10.0.1的验证）。

流将排序操作委托给相应的Arrays.sort方法（请参见各种SortingOps的end方法）。

对象流的排序

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

作者认为Python中列表排序的Tim Peter实现是他们的灵感来源，进一步将这个想法归功于论文"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。

但是用户还可以通过将java.util.Arrays.useLegacyMergeSort属性设置为true来请求使用MergeSort（在OpenJDK 10中，当数组小于等于32个元素时将回退到插入排序）。这个计划在未来的版本中删除。

原始类型流的排序

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

来源

要了解更多，请参见OpenJDK代码：

• SortedOps.java - 与流相关的实现

• Arrays.java - Arrays 帮助类的实现，包括不同的 sort 方法

• TimSort.java - TimSort 的实现

• ComparableTimSort.java - 实现了对实现了Comparable 接口的类进行排序的变体

• DualPivotQuicksort.java - 对基本数据类型进行排序的实现

- mszymborski

---

非常有趣的算法。我现在会研究这个算法 :) - Ad Infinitum

当我尝试进行测试时，我总是发现流.sorted更快。for(int i = 0;i < 10000;i++) { arr[i] = (int) Math.random(); } IntStream stream1 = Arrays.stream(arr); long sttime = System.nanoTime(); Arrays.sort(arr); long endtime = System.nanoTime(); long sttime1 = System.nanoTime(); stream1.sorted(); long endtime1 = System.nanoTime(); System.out.println(sttime - endtime); System.out.println(sttime1 - endtime1);如果您知道原因，请详细说明。 - Yogesh Kumar Gupta