Java - Collections.sort（）性能 [英] Java - Collections.sort() performance
问题描述
使用 Collections.sort（）来排序一个LinkedList，它的元素实现了Comparable接口，因此它们按照自然顺序排序。在javadoc文档中，它表示此方法使用具有n * log（n）性能的 mergesort 算法。
我的问题是如果有一个更有效的算法来排序我的LinkedList？
此列表的大小可能非常高，排序也很频繁。
谢谢！ / p>
O（N log N）也就是说，存在线性时间 O（N）不基于比较的排序，例如。计数排序和桶排序。这是有用的。你排序了数百万和数百万的整数，但它们在1..10之间。
此外，如果列表是几乎排序，否则二次插入sort在某些情况下实际上会更好。
这是否适用，甚至是否值得实现，取决于您的分析结果。
另请参阅
- 维基百科/计数排序
- 维基百科/桶排序
ul>
相关问题
Im using Collections.sort() to sort a LinkedList whose elements implements Comparable interface, so they are sorted in a natural order. In the javadoc documentation its said this method uses mergesort algorithm wich has n*log(n) performance.
My question is if there is a more efficient algorithm to sort my LinkedList?
The size of that list could be very high and sort will be also very frequent.
Thanks!
O(N log N) is very good asymptotically. That said, there are linear time O(N) non-comparison based sort, e.g. counting sort and bucket sort. This is useful when, e.g. you're sorting millions and millions of integers, but they're between 1..10.
Also, if the list is "almost sorted", the otherwise quadratic insertion sort is reported to actually be better under some scenarios.
Whether or not this is applicable, or even worth to implement, depends on your profiling results. I'd say that unless it shows the sort to be a bottleneck, don't worry about it.
See also
Related questions
这篇关于Java - Collections.sort（）性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
