问Collections#sort方法在Java中的时间复杂度是多少？

EN

这取决于您使用的Java.log的版本。，但最终，大O时间复杂度仍然是O(N*(N))。

对于Java 6，它是mergesort的修改版本。请查看此处的描述：Collections#sort for Java 6

排序算法是一种改进的合并排序(其中，如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并)。该算法提供了有保证的n log(n)性能。指定的列表必须是可修改的，但不必是可调整大小的。此实现将指定的列表转储到一个数组中，对该数组进行排序，然后遍历该列表，从该数组中的相应位置重置每个元素。这避免了尝试就地对链表进行排序所导致的n2 (N)性能。

对于 Java 7，它得到了改进：由于enhancement，Collections#sort for Java 7。请注意，TimSort的最佳情况为 O(N)，并且被证明比之前的实现更快。

实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要的比较次数远少于 n lg(n)，而当输入数组是随机排序时，它提供了传统归并排序的性能。如果输入数组接近排序，则实现需要大约 n 次比较。临时存储要求从几乎排序的输入数组的小常数到随机排序的输入数组的 n/2 对象引用不等。

该实现在其输入数组中同等地利用升序和降序，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。

该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。它使用了 Peter McIlroy 在 1993 年 1 月第四届 ACM-SIAM 离散算法年度研讨会论文集上的“乐观排序和信息论复杂性”中的技术。

这个实现将指定的列表转储到一个数组中，对数组进行排序，并遍历列表，从数组中的相应位置重置每个元素。这避免了由于尝试对链表进行排序而导致的 n2 log(n) 性能。

对于10^6的ArrayList，这是一种好的排序方法吗？

从理论上讲，它足以使用。但这让我想知道为什么你必须对内存中的数据进行排序。如果数据来自数据库，则使用索引列/字段对其进行排序，否则请检查您是否知道将用于排序的字段的一些特征，以及是否可以使用O(N)时间复杂度算法，如Bucket Sort或Radix Sort。当没有其他方法时，使用Collections#sort。

Collections.sort()的时间复杂度为O(n*log(n))，使用Collections.sort()排序的列表只会在调用sort()之后进行排序。

集合文档中的信息-

排序算法是一种改进的合并排序(其中，如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并)。该算法提供了有保证的n log(n)性能。