Java – Collections.sort（）性能
我使用Collections.sort（）对其元素实现Comparable接口的LinkedList进行排序，因此它们按自然顺序排序。 在javadoc文档中，它表示此方法使用具有n * log（n）性能的mergesort算法。
我的问题是，是否有更有效的算法来排序我的LinkedList？
该列表的大小可能非常高，排序也会非常频繁。
谢谢！
O(N log N)渐近非常好。 也就是说，存在线性时间O(N)非基于比较的排序，例如计数排序和桶排序。 例如，当您对数百万个整数进行排序时，这很有用，但它们介于1..10之间。
此外，如果列表“几乎已排序”，则在某些情况下报告的其他二次插入排序实际上更好。
这是否适用，或者甚至值得实施，取决于您的分析结果。 我会说，除非它显示出这种瓶颈，否则不要担心。
也可以看看
- 维基百科/计数排序
- 维基百科/ Bucket排序
相关问题
- 是否有O（n）整数排序算法？
如果你说列表将“非常频繁”排序，你应该考虑一直按照排序的状态保存列表，比如使用树而不是LinkedList 。 如果你没有任何重复的值并且不需要任何List操作（因为你一直在对它们进行排序），你甚至可以使用一些SortedSet而不是List 。 检查SortedSet实现的TreeSet类。
此实现为基本操作（添加，删除和包含）提供了有保证的log（n）时间成本。
如果你想迭代这个“列表”（实际上是一个Set），你可以使用该类的Iterator。
以升序返回此集合中元素的迭代器。
如果你在List中有重复的值你必须使用一些技巧（比如将值放在一个新的类中，它也有一些delta用于排序相等的对象）
没有比n*log(n)更好的通用排序算法。 这很快。 一般来说，我的意思是您的数据没有特殊属性。
我正在试验大型数据集（GB数据）并实现了合并排序（有一个很好的例子@ googlecode）。 但是，我正在使用Collection.sort（）对我的临时缓冲区进行预排序，根据我的经验，Collection.sort（）在某个数据阈值处变得非常慢。 使用96MB的辅助缓冲区，我可以在大约30秒内对其中一个缓冲区进行排序（注意：这在很大程度上取决于您使用的比较器 – 我使用带有相当复杂的列解析器的自定义列布局），但是将其增加到128MB块大小时间跳到3分钟以上。 这与我可以针对较小的块观察到的线性（或接近线性）行为无关。 这有很大影响，几乎（？）所有情况下使用较小缓冲区的合并排序比使用128MB缓冲区的内存排序更快。 简而言之：合并排序是超过100MB边界的大型数据集的方法。 我无法回答为什么会这样，而且这些数字甚至可能与机器有关（我的是2.6GHz i7和16GB内存的OS-X）。
在排序列表方面，不，所有基于比较的一般数据排序都是O（N log（N））。
如果您的求助是由于插入，那么您可以尝试批量插入然后合并排序与主列表 – 如果你有B个新项目，你在O（B日志（B））中排序然后进行单级合并两个列表中的O（N + B）。
如果您的求助是由于项目值的变化，如果您将可变值更改为不可变值并将更改视为一批插入和删除，则可能可以执行类似的批处理。 否则，您将无法避免对整个列表进行排序。
如果您的要求允许，那么有各种非链表列表结构，例如TreeSet可用，它可以更有效地维护排序顺序，但如果值是可变的则会失败。