java - Java - 在已经排序的列表上调用 sort() 是 O(1) 操作吗？

Question

Collections.sort(list)检查是否已经list排序，或者是否出于其他原因可能是 O(1)？或者，在调用/向列表中添加元素时对标志进行排序并将其设置为/
是个好主意吗？truefalsesort()

Answer 1

如何不查看列表就确定是否已排序？不会的O(1)。确定列表是否已排序至少需要O(n).

这意味着 IfCollections.sort确实费心检查列表是否首先排序，每个排序操作平均需要O(n) + O(n log n).

Answer 2

事实上，在 Java7 中，Java 已经从合并排序切换到TimSort（以首先为 cpython 实现它的 python 开发人员 Tim Peters 命名）来处理一些排序任务。

虽然不是 O(1)，但使用 TimSort 对已排序或​​部分排序的列表进行排序比对完全随机数据集进行排序更有效（因为后者没有比O(n log n)比较排序更有效的方法，但对于不是随机数据）。

Answer 3

不可能是 O(1)，你无法检查集合的排序是否比 O(n) 快。有一面旗帜应该没问题，但如果不知道你到底在做什么，就很难确定。

Answer 4

一般来说，对已经排序的列表进行排序并不会使其更快（除了像冒泡排序这样的简单排序）在某些情况下，预排序会更慢。

在 Collections.sort() 的情况下，对已排序列表进行排序并不快。