Collections.Sort 后续排序的性能？
我将 Collections.sort 与自定义比较器类一起使用。我听说这有 O(N log N) 运行时复杂度。我很想知道当集合没有改变时后续排序会发生什么。
举例来说，假设我有一个 Egg 的 ArrayList，每个都有一个近似的 size 字段（我的比较器根据该字段进行排序）。如果我将十个鸡蛋插入数组列表中并对其进行排序，则预计需要 O(N log N) 时间。
如果我再次排序，而不添加、删除或更改任何元素，是否仍需要 N log N 时间？
I'm using Collections.sort with a custom comparator class. I've heard that this has O(N log N) runtime complexity. I'm curious to know what happens on subsequent sorts when the collection hasn't changed.
By example, lets say I have an ArrayList of Eggs, each which has an approximate size field (which my comparator sorts by). If I insert ten eggs into the array list, and sort it, I can expect it to take O(N log N) time.
If I sort it again, without adding, removing, or changing any elements, will it still take N log N time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
Javadoc< /a> 表示“如果低子列表中的最高元素小于高子列表中的最低元素，则忽略合并”。这似乎意味着什么也没有发生，所以它应该更快。
你总是可以测试它。
The Javadoc says 'the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist'. That appears to mean nothing happens so it should be quicker.
You could always test it.
我还没有分析过当前sun java库中的代码。然而，javadoc 声明使用了合并排序。大多数合并排序在已排序的集合上产生 O(n) 性能。尽管文档中没有说明这一点。我的个人经验表明我在排序或接近排序的列表上表现非常好。
I have not analysed the code in the current sun java library. However, the javadoc states that a merge sort is used. Most merge sorts yield a O(n) performance on already sorted collection. Although this is not stated in the documentation. My personal experience has shown me really good performance on sorted or nearly sorted lists.
Per JavaDoc Collections.sort 使用合并排序算法。
您可以在这里亲自查看它的效果 -> http://www.sorting-algorithms.com/
Per JavaDoc Collections.sort uses merge sort algorithm.
You can see how it does, for yourself, here -> http://www.sorting-algorithms.com/
为了扩展 EJP 的答案，如果文档表明合并过程是跳过的步骤，那么在这种最佳情况下，运行时将为 LG N，因为它仍然会将列表分解为 LG N 子问题。相对于线性扫描的倍增就是效率的提升。
To expand on EJP's answer, if the documentation indicates that the merge pass is the step skipped, then in this best case runtime would be LG N because it will still break the list into LG N subproblems. The multiplication against the linear scan is the improvement in efficiency.