java中Collections＃sort方法的时间复杂度是多少？
java中Collections#sort方法的时间复杂度是多少？ 使用哪种算法？
Collection#sort是排序10 ^ 6的ArrayList的好方法吗？
这取决于您使用的Java版本。 但最终，Big-O时间复杂度仍为O（N * log（N））。
对于Java 6，它是mergesort的修改版本。 请查看此处的说明： Collections#sort for Java 6
排序算法是修改后的mergesort（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。 该算法提供有保证的n log（n）性能。 指定的列表必须是可修改的，但无需resize。 此实现将指定的列表转储到数组中，对数组进行排序，并迭代列表，从数组中的相应位置重置每个元素。 这样可以避免尝试对链接列表进行排序所导致的n2 log（n）性能。
对于Java 7，它得到了改进： Collections#sort for Java 7由于增强 。 请注意， TimSort具有O（N）的最佳情况，并且certificate比先前的实现更快。
实现注意事项：此实现是一个稳定的，自适应的迭代合并输出，当输入数组部分排序时，需要远远少于n lg（n）的比较，同时在输入数组随机排序时提供传统mergesort的性能。 如果输入数组几乎已排序，则实现需要大约n次比较。 临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的n / 2个对象引用不等。
该实现在其输入数组中具有升序和降序的相同优势，并且可以利用同一输入数组的不同部分中的升序和降序。 它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。
该实现改编自Tim Peters的Python排序（ TimSort ）。 它使用了Peter McIlroy的“乐观排序和信息理论复杂性”中的技术，参见“第四届年度ACM-SIAM离散算法研讨会论文集”，第467-474页，1993年1月。
此实现将指定的列表转储到数组中，对数组进行排序，并迭代列表，从数组中的相应位置重置每个元素。 这样可以避免尝试对链接列表进行排序所导致的n2 log（n）性能。
这是一个排序10 ^ 6的
ArrayList的好方法吗？
从理论上讲，它足以使用。 但这让我想知道你为什么要在内存中对数据进行排序。 如果数据来自数据库，则使用索引列/字段对其进行排序，否则检查您是否知道将用于排序的字段的某些特征，以及是否可以使用O（N）时间复杂度算法（如Bucket Sort）或Radix排序 。 如果没有别的办法，请使用Collections#sort 。
Collections.sort（）的时间复杂度为O（n * log（n）），使用Collections.sort（）排序的列表只能在调用sort（）后才会对集合文档中存在的信息进行排序 – “排序算法是一个修改过的mergesort（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并。）该算法提供有保证的n log（n）性能。“