Java - Collections.sort（） performance
2022-09-02 20:23:45
我正在使用 Collections.sort（） 对一个 LinkedList 进行排序，其元素实现了可比较的接口，因此它们按自然顺序排序。在javadoc文档中，它说这种方法使用具有n * log（n）性能的mergesort算法。
我的问题是，是否有更有效的算法来对我的LinkedList进行排序？
该列表的大小可能非常高，排序也将非常频繁。
答案 1
O(N log N)渐近非常好。也就是说，存在线性时间非基于比较的排序，例如计数排序和桶排序。例如，当您对数百万和数百万个整数进行排序时，这很有用，但它们介于 1..10 之间。O(N)
此外，如果列表是“几乎排序”的，则报告在某些情况下，其他二次插入排序实际上更好。
这是否适用，甚至是否值得实施，取决于您的分析结果。我想说的是，除非它显示出瓶颈，否则不要担心它。
另请参见
相关问题
答案 2
如果您说列表将“非常频繁”地排序，则应考虑始终以排序状态保存列表，例如使用树而不是.如果您没有任何重复的值并且不需要任何List操作（因为您一直在对它们进行排序），也许您甚至可以使用一些而不是一个。。检查实现的树集类。LinkedListSortedSetListSortedSet
此实现为基本操作（添加、删除和包含）提供有保证的 log（n） 时间成本。
如果要迭代此“列表”（实际上是一个集合），则可以使用该类的迭代器。
按升序返回此集中元素的迭代器。
如果列表中有重复的值，则必须使用一些技巧（例如将值放入一个新类中，该类也获得了一些用于对相等对象进行排序的增量）
推荐
