问Java ().sorted或list.sort()是否会增加时间复杂度？

EN

这些方法的时间复杂度为O(nlog(n))。这是排序数组的最佳时间复杂度。

使用嵌套循环的排序算法通常是O(n²)复杂性的，因为内部循环的每一次迭代都发生在外部循环的每一次迭代中。其中一些算法将是

• 插入排序；
• 气泡分类；
• 等等；

但是，其他的不使用嵌套循环，例如，最常用的排序算法是QuickSort，它作为一个除法和征服算法，它首先选择一个枢轴值并根据所述的枢轴值重新排列数组，所有较小的值都在它前面，所有较大的值都在它之后(还不一定是有序的)。

QuickSort是O(nlog(n))的平均案例复杂度。请记住，一些更高级的排序算法也有一个最坏的场景复杂性的O(n^2)。

事实上，一些排序实现实际上在排序数组之前对其进行了洗牌，以避免出现最坏的情况。

我在这里留下一些关于快速排序的信息。

快速排序解释及其工作原理

，，你必须理解的关于任何算法的第一件阳痿的事情，就是，仅仅谈论算法，，不会显着地改变你在这个领域的知识。

您必须study and practice them，逐步实现算法。

如果想要提高对排序算法的理解，就需要从非常基本的bubble sort和insertion sort开始(在Wikipedia中可以找到描述和伪代码就足以掌握这种思想并开始编码)。当您对准备使用merge sort和快速排序的基本知识有了坚定的了解时。

这里有一个小小的洞察力介绍了JDK提供的所谓双枢轴快速排序内部正在发生的事情。

事实上，这是一个非常advanced compound algorithm，除了传统的快速排序需要merge sort、heap sort和parallel computing来处理大量的数据集。

只有当你知道基本算法的所有proc and cons (比如为什么有不同的分配方案，为什么更喜欢快速排序而不是合并排序，而在更糟糕的情况下，合并排序的时间复杂度似乎更好，等等)，才有理由猜测正在采用双枢轴快速排序的optimizations。

关于内置快速排序的性能，现在简短地回答如下：

在任何数据上保证n*log(n)

Now about Streams and sorting.

排序总是发生在inside the array就位。如果数据源由数组(一个ArrayList或CopyOnWriteArrayList )支持，那么它的底层数组将被排序。

否则，例如，如果您使用LinkedList拨号，将在内存中分配一个新的数组，列表中的所有数据将被复制到该数组中，然后进行排序。

当您使用stream拨号时，它将是数据的not affect the source。源中的整个数据需要加载到内存中以进行排序。然后你很可能会把它储存在一个品牌收藏中。

结论：

• 如果您需要更改数据源--直接使用sort()方法和列表；
• 如果您的任务不需要对所有初始数据进行排序(或者您只是希望保留源的初始状态)，那么Stream API将帮助您进行筛选和排序。