哪种算法在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

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

Answer 1

下面的答案与OpenJDK相关(根据10.0.1检查).

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

对对象流进行排序

对于排序对象,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可以通过设置java.util.Arrays.useLegacyMergeSort属性来请求(在阵列足够小时回退到插入排序 - 在OpenJDK 10中,它是32个或更少的元素)true.计划在将来的版本中删除.

对基元流进行排序

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

来源

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

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

• Arrays.java - Arrays帮助器的实现,请参阅不同的sort方法

• TimSort.java - TimSort的实现

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

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