java - Collections.Sort 对后续排序的性能？

Question

我正在使用 Collections.sort使用自定义比较器类。我听说这有 O(N log N)运行时复杂度。我很想知道当集合没有改变时后续排序会发生什么。

例如，假设我有一个 Egg 的 ArrayList s，每个都有一个近似 size字段(我的比较器按其排序)。如果我在数组列表中插入 10 个鸡蛋并对其进行排序，我可以预期它需要 O(N log N)时间。

如果我再次排序，不添加、删除或更改任何元素，是否仍然需要 N log N时间？

Answer 1

Javadoc说“如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并”。这似乎意味着什么也没有发生，所以它应该更快。

你总是可以测试它。