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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Java中的Collections#sort方法的时间复杂度是多少？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2869字，纯文字阅读大概需要5分钟。

内容图文

这个问题已经在这里有了答案：            >            What is the time complexity of java.util.Collections.sort() method?                                    4个
Java中的Collections#sort方法的时间复杂度是多少？使用哪种算法？

Collection#sort是对10 ^ 6的ArrayList进行排序的好方法吗？

解决方法:

这取决于您使用的Java版本.但是最后,Big-O时间复杂度仍然是O(N * log(N)).

对于Java 6,它是mergesort的修改版本.在这里查看说明：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,已进行了改进：由于enhancement而导致的改进为：Collections#sort for 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 ( 07004). 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.

内容总结

以上是互联网集市为您收集整理的Java中的Collections#sort方法的时间复杂度是多少？全部内容，希望文章能够帮你解决Java中的Collections#sort方法的时间复杂度是多少？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端