由网友(狗要走我不留)分享简介：即时通讯使用Collections.sort()排序在LinkedList，它的元素实现Comparable接口，因此它们按自然顺序。在Javadoc文档它说，这种方法使用的归并的算法至极具有的n * log（n）性能。 Im using Collections.sort() to sort a LinkedList...

即时通讯使用Collections.sort()排序在LinkedList，它的元素实现Comparable接口，因此它们按自然顺序。在Javadoc文档它说，这种方法使用的归并的算法至极具有的n * log（n）性能。

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.

我的问题是，如果有一个更有效的算法进行排序我的LinkedList？

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.

谢谢！

推荐答案

O（N日志N）是非常好的渐近。这就是说，有线性时间 O（N）非基于比较的排序，如计数排序和桶排序。这是非常有用的时候，例如你排序整数数以百万计，但他们1..10之间。

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.

维基/计数排序 维基/桶排序 Wikipedia/Counting sort Wikipedia/Bucket sort 是否有一个O（n）的整数排序算法？