java中Collections＃sort方法的时间复杂度是多少？ [英] What is the time complexity of Collections#sort method in java?
问题描述
java中集合#sort 方法的时间复杂度是多少？使用了哪种算法？
What is the time complexity of Collections#sort method in java? Which algorithm is used?
Collection＃sort 排序 ArrayList的好方法 10 ^ 6？
Is Collection#sort a good method for sorting an ArrayList of 10^6?
推荐答案
这取决于您使用的Java版本。 但最后，Big-O时间复杂度仍为O（N * log（N））。
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 6，它是修改后的版本mergesort。请查看此处的说明： 集合#sort for Java 6
For Java 6, it's a modified version of mergesort. Check the description here: Collections#sort for Java 6
排序算法是一个经过修改的mergesort（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。该算法提供有保证的n log（n）性能。指定的列表必须是可修改的，但无需调整大小。此实现将指定的列表转储到数组中，对数组进行排序，并迭代列表，从数组中的相应位置重置每个元素。这样可以避免因尝试对链接列表进行排序而导致的n2 log（n）性能。
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.
对于Java 7，它改进了： 集合#sort for Java 7 / JDK-6804124rel =noreferrer>增强。请注意， TimSort 具有O（N）的最佳案例，并且证明比以前的实施更快。
For Java 7, it was improved: Collections#sort for Java 7 due to enhancement. Note that TimSort has a best case of O(N) and proves to be faster than the previous implementation.
实现注意事项：此实现是一个稳定的，自适应的迭代合并输出，当输入时需要远低于n lg（n）的比较数组是部分排序的，同时在输入数组随机排序时提供传统mergesort的性能。如果输入数组几乎排序，则实现需要大约n次比较。临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的n / 2个对象引用不等。
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.
该实现改编自Tim Peters的Python列表排序（ TimSort ）。它使用了Peter McIlroy的乐观排序和信息理论复杂性中的技术，参见第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年1月。
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.
此实现将指定的列表转储到数组中，对数组进行排序，并迭代列表，从数组中的相应位置重置每个元素。这样可以避免因尝试对链接列表进行排序而导致的n2 log（n）性能。
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.
这是一个很好的方法来排序
ArrayList10 ^ 6？
从理论上讲，它足以使用。但这让我想知道你为什么要在内存中对数据进行排序。如果数据来自数据库，则使用索引列/字段对其进行排序，否则检查您是否知道将用于排序的字段的某些特征，以及是否可以使用O（N）时间复杂度算法，如 Bucket Sort 或基数排序。如果没有其他办法，请使用集合#sort 。
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 Sort or Radix Sort. When there's no other way, use Collections#sort.
这篇关于java中Collections＃sort方法的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
