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

我写了以下课程：

public class SortingObjectsWithAngleField implements Comparator { 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”和“angle”字段的对象。

然后我用：

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

这种排序方法的复杂性是什么？

Answer 1

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

排序算法是修改后的mergesort（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。 该算法提供有保证的n log（n）性能。

你的比较器并没有改变这种复杂性，除非你对你的集合中的循环做任何事情，你不这样做。

Answer 2

您应该在API中找到它： n log（n） 。

Answer 3

摘自Collections.sort –

排序算法是修改后的mergesort（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。 该算法提供有保证的n * log（n）性能

Answer 4

每个人都说明了API文档 ，添加了一些我发现的相关信息。

如果提供自定义比较器，则使用mergesort的修改版本（也称为timsort ）。 该实现已从python的列表排序中借用。

在最好的情况下，只需要n-1次比较，所以best case is O(n)并且guaranteed performance in all the cases is O(n.lg(n))