java.util.Collections.sort()方法的时间复杂度是多少？

Question

我写了以下课程：

public class SortingObjectsWithAngleField implements Comparator<Point> {  
    public int compare(Point p1, Point p2) {
        double delta = p1.getAngle() - p2.getAngle();
        if(delta == 0.00001)
            return 0;
        return (delta > 0.00001) ? 1 : -1;
    }
}

然后，在我的

main()

方法中，我创建了一个

List

，向其中添加了一些具有“X”和“角度”字段的对象。

然后我使用：

Collections.sort(list, new SortingObjectsWithAngleField());

这种排序方法的复杂度是多少？

Answer 1

您可以阅读有关集合排序的文档，但这里适合您：

排序算法经过修改 合并排序（其中合并是 如果最高元素被省略 low 子列表小于最低的 高子列表中的元素）。这 算法提供有保证的 n log(n) 性能。

您的比较器不会改变这种复杂性，除非您对其中的集合进行循环操作，而您却没有这样做。

Answer 2

您应该在 API 中找到它：n log(n)。

Answer 3

取自 Collections.sort -

排序算法经过修改 合并排序（其中合并是 如果最高元素被省略 low 子列表小于最低的 高子列表中的元素）。这 算法提供有保证的 n*log(n) 性能

Answer 4

每个人都陈述了API文档，添加了一些我找到的更相关的信息。

如果您提供自定义比较器，则使用合并排序的修改版本（也称为

timsort

）。该实现借用自 python 的列表排序。

在最好的情况下，只需要 n-1 次比较，因此

best case is O(n)

和

guaranteed performance in all the cases is O(n.lg(n))

Answer 5

从 JDK 8 开始，

Collections.sort

方法委托给

List.sort

方法，该方法具有以下描述：

此实现是一种稳定、自适应、迭代的归并排序，当输入数组部分排序时，需要的比较次数远少于 n lg(n) 次，同时在输入数组随机排序时提供传统归并排序的性能。

这与 JDK 7 中的

Collections.sort

方法的描述完全相同。

因此，在最坏的情况下，

Collections.sort

 的性能与归并排序一样好，其时间复杂度为 

O(n*log(n))。

稍后在描述中我们看到

如果输入数组接近排序，则实现需要大约 n 次比较。

该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。

（有关详细信息，请参阅维基百科上的

Timsort）。