当前位置：技术文章 > 编程面试题 >

Java-Collections.sort（）性能

问题内容：

我使用Collections.sort（）对LinkedList进行排序，其元素实现Comparable接口，因此它们以自然顺序排序。在javadoc文档中，该方法使用具有n * log（n）性能的 mergesort 算法。

我的问题是是否有一种更有效的算法对我的LinkedList进行排序？

该列表的大小可能很大，排序也将非常频繁。

谢谢！

问题答案：

O(N log N)渐近地非常好也就是说，存在O(N)基于线性时间非比较的排序，例如计数排序和存储桶排序。例如，当您要对数百万个整数进行排序，但它们之间的整数在1..10之间时，此功能很有用。

同样，如果列表是“几乎已排序的”，则在某些情况下，其他情况下的二次插入排序实际上会更好。

这是否适用，甚至值得实施，取决于您的分析结果。我要说的是，除非它显示出瓶颈，否则请不要担心。