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

Question

Collections#sort的时间复杂度是多少Java 中的方法？使用哪种算法？

是Collection#sort排序 ArrayList 的好方法10^6？

Answer 1

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

对于 Java 6，它是合并排序的修改版本。检查此处的描述:Collections#sort for 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.

对于 Java 7，它得到了改进:Collections#sort for Java 7 由于 enhancement 。请注意，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.

<小时/>

Is this a good method for sorting an ArrayList of 10^6?

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