Stream接口中使用排序方法的算法 [英] Which algorithm use sorted method in Stream interface

问题描述

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

When I print the values in the sorted method,

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

我无法理解这里排序算法的逻辑.任何帮助将不胜感激.

I could not understand the logic of the sorting algorithm here. Any help will be appreciated.

推荐答案

以下答案与 OpenJDK 相关(针对 10.0.1 进行了检查).

The answer below is relevant to OpenJDK (checked against 10.0.1).

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

Streams delegate the sorting operations to the relevant Arrays.sort methods (see end methods of various SortingOps).

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

For sorting objects, TimSort (basically a merge sort which uses insertion sort when the divisions of the input are small enough) is the preferred method.

作者将 Tim Peter 在 Python 中实现的列表排序归功于灵感，进一步将这个想法归因于论文 乐观排序和信息理论复杂性"，Peter McIlroy，SODA(第四届年度 ACM-SIAM 离散算法研讨会)，467-474，德克萨斯州奥斯汀，25-1993 年 1 月 27 日.

The authors credit Tim Peter's implementation of list sort in Python as an inspiration, further attributing the idea to the paper "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.lang.util.Arrays.useLegacyMergeSort 属性为 true.计划在未来的版本中删除.

However the user can also request MergeSort (falling back to insertion sort when the arrays are small enough - in OpenJDK 10 it's 32 or fewer elements) to be used by setting the java.util.Arrays.useLegacyMergeSort property to true. This is planned to be removed in future releases.

用于对原语流进行排序(byte、char、short、int、long, float, double) - 实现了双枢轴快速排序.作者(Vladimir Yaroslavskiy、Jon Bentley 和 Josh Bloch)没有提供更多有关灵感来自何处的信息.

For sorting streams of primitives (byte, char, short, int, long, float, double) - dual pivot quicksort is implemented. The authors (Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch) do not give any more information about where the inspiration came from.

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

To learn more, see OpenJDK code:

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

Arrays.java - Arrays 助手的实现，查看不同的 sort 方法

Arrays.java - implementation of the Arrays helper, see the different sort methods

TimSort.java - TimSort 的实现

TimSort.java - implementation of TimSort

ComparableTimSort.java - 实现 Comparable

DualPivotQuicksort.java - 原语排序的实现

这篇关于Stream接口中使用排序方法的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！