java.util.stream.Stream的大O复杂性 .sorted（）

有谁知道java.util.stream.Stream.sorted()的时间复杂度是多少？

Answer 1

好吧， sorted()本身就是O（1），因为它是一个不消耗流的中间操作，只是简单地向管道添加一个操作。

一旦终端操作消耗了流，就会发生排序

• 它没有做任何事情（O（1）），因为流知道元素已经排序（例如，因为它们来自SortedSet）
• 或者流不是并行的，它委托给Arrays.sort() （O（n log n））
• 或者流是并行的，它委托给Arrays.parallelSort() （O（n log n））

Answer 2

从JDK 8开始，主要的排序算法也是用于顺序排序的标准流API实现的TimSort 。 最坏的情况是O(n log n) ，但是如果数据被预先排序（正向或反向）或部分预分类（例如，如果连接两个已排序的话O(n log n) ，它的工作速度非常快（使用O(n)和非常小的常数）列出并再次排序）。