Java.util.stream.Stream<T>.sorted() 的时间复杂度为 Big-O。

Question

有人知道 java.util.stream.Stream<T>.sorted() 的时间复杂度吗？

- hackie

---

“Stream”是一个接口。它完全取决于实现方式。 - Obicere

Answer 1

嗯，sorted() 本身是 O(1)，因为它是一个中间操作，不会消耗流，而只是向管道添加一个操作。

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

• 如果流知道元素已经排序（例如来自SortedSet），则不执行任何操作（O(1)）
• 如果流不是并行的，则委托给 Arrays.sort() （O(n log n)）
• 如果流是并行的，则委托给 Arrays.parallelSort() （O(n log n)）

- JB Nizet

Answer 2

从JDK 8开始，主要的排序算法也被用于标准流API实现的顺序排序中，这个算法是TimSort。它的最坏情况是O(nlogn)，但如果数据已经排好序（向前或向后）或部分排好序（例如，如果您连接了两个排序列表并再次对其进行排序），则它可以非常快地工作（具有O(n)和相当小的常数）。

- Tagir Valeev