java中Collections#sort方法的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25492648/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the time complexity of Collections#sort method in java?
提问by user3972937
What is the time complexity of Collections#sortmethod in java? Which algorithm is used?
Collections#sortjava中方法的时间复杂度是多少？使用哪种算法？
Is Collection#sorta good method for sorting an ArrayListof 10^6?
是Collection#sort一种ArrayList对 10^6进行排序的好方法吗？
采纳答案by Luiggi Mendoza
This depends on the version of Java you use.But in the end, the Big-O time complexity is still O(N*log(N)).
这取决于您使用的 Java 版本。但最终，Big-O 的时间复杂度仍然是 O(N*log(N))。
For Java 6, it's a modified version of mergesort. Check the description here: Collections#sortfor Java 6
对于 Java 6，它是合并排序的修改版本。检查这里的描述：Collections#sort对于 Java 6
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.
排序算法是一种改进的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。该算法提供有保证的 n log(n) 性能。指定的列表必须是可修改的，但不需要可调整大小。此实现将指定的列表转储到数组中，对数组进行排序，并遍历列表，从数组中的相应位置重置每个元素。这避免了因尝试对链接列表进行排序而导致的 n2 log(n) 性能。
For Java 7, it was improved: Collections#sortfor Java 7due to enhancement. Note that TimSorthas a best case of O(N) and proves to be faster than the previous implementation.
对于 Java 7，它进行了改进：Collections#sort对于 Java 7由于增强。请注意，TimSort具有 O(N) 的最佳情况，并且证明比之前的实现更快。
Implementation note: This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array.
The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techiques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993.
This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.
实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要的比较次数远少于 n lg(n) 次，同时在输入数组随机排序时提供传统归并排序的性能。如果输入数组几乎已排序，则实现需要大约 n 次比较。临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的 n/2 个对象引用不等。
该实现在其输入数组中平等地利用升序和降序，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个已排序的数组：只需连接数组并对结果数组进行排序。
该实现改编自 Tim Peters 的 Python 列表排序 ( TimSort)。它使用来自 Peter McIlroy 的“乐观排序和信息理论复杂性”的技术，在第四届 ACM-SIAM 离散算法研讨会论文集，第 467-474 页，1993 年 1 月。
此实现将指定的列表转储到数组中，对数组进行排序，并遍历列表，从数组中的相应位置重置每个元素。这避免了因尝试对链接列表进行排序而导致的 n2 log(n) 性能。
Is this a good method for sorting an
ArrayListof 10^6?
这是
ArrayList对 10^6进行排序的好方法吗？
In theory, it is enough to use. But this makes me wonder why would you have to sort the data in memory. If the data comes from a database, then sort it there using an indexed column/field, otherwise check if you know some characteristics of the field you will use for sorting and if you may use a O(N) time complexity algorithm like Bucket Sortor Radix Sort. When there's no other way, use Collections#sort.
理论上，使用就够了。但这让我想知道为什么必须对内存中的数据进行排序。如果数据来自数据库，则使用索引列/字段对其进行排序，否则请检查您是否知道将用于排序的字段的某些特征，以及是否可以使用 O(N) 时间复杂度算法，例如Bucket Sort或基数排序。当没有其他方法时，请使用Collections#sort.
回答by Ekwinder Saini
The time complexity of Collections.sort() is O(n*log(n)) and a list sorted with Collections.sort() will only be sorted after the call to sort() Info present in collections docs - "The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance."
Collections.sort() 的时间复杂度为 O(n*log(n)) 并且使用 Collections.sort() 排序的列表只会在调用集合文档中的 sort() Info 之后进行排序 - “排序算法是一种修改后的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并。该算法保证了 n log(n) 性能。”
