Java - Collections.sort()性能

Question

我使用Collections.sort()对其元素实现Comparable接口的LinkedList进行排序,因此它们按自然顺序排序.在javadoc文档中,它说这个方法使用具有n*log(n)性能的mergesort算法.

我的问题是,是否有更有效的算法来排序我的LinkedList？

该列表的大小可能非常高,排序也会非常频繁.

谢谢!

Answer 1

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

此外,如果列表"几乎已排序",则在某些情况下报告的其他二次插入排序实际上更好.

这是否适用,或者甚至值得实施,取决于您的分析结果.我会说,除非它显示出这种瓶颈,否则不要担心.

也可以看看

• 维基百科/计数排序
• 维基百科/ Bucket排序

相关问题

• 是否有O(n)整数排序算法？

Answer 2

如果你说列表将"非常频繁"排序,你应该考虑一直按照排序的状态保存列表,比如使用树而不是a LinkedList.如果你没有任何重复的值并且不需要任何List操作(因为你总是对它们进行排序),也许你甚至可以使用一些SortedSet而不是a List.检查实现的TreeSet类SortedSet.

此实现为基本操作(添加,删除和包含)提供了有保证的log(n)时间成本.

如果你想迭代这个"列表"(实际上是一个Set),你可以使用该类的Iterator.

以升序返回此集合中元素的迭代器.

如果List中有重复的值,你必须使用一些技巧(比如将值放在一个新类中,该类也有一些delta用于排序相等的对象)