Java - 在已排序的列表上调用sort()进行O(1)操作？

Question

请问Collections.sort(list)检查,如果list已经排序或者是它也许O(1)其他原因？
或者,将标志排序并将其设置为true/ false在调用sort()/向列表中添加元素时,这是一个好主意吗？

Answer 1

如何在不查看列表的情况下确定是否排序？它不会O(1).确定列表是否已排序至少需要O(n).

这将意味着如果Collections.sort确实需要检查列表是否排序,那么每个排序操作都需要平均O(n) + O(n log n).

Answer 2

实际上，对于Java7，Java已从mergesort切换到TimSort（以python开发人员Tim Peters的名字命名，后者首先为cpython实现了它）来执行某些排序任务。

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