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

2022-09-01 14:05:00

我写了以下类:

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;
    }
}

然后,在我的方法中,我创建了一个,我向其中添加了一些具有“X”和“角度”字段的对象。main()List

然后我使用:

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

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


答案 1

您可以阅读集合排序上的文档,但这里适合您:

排序算法是修改后的合并排序(如果低子列表中的最高元素小于高子列表中的最低元素,则省略合并)。此算法提供有保证的 n 个 log(n) 性能。

您的比较器不会改变这种复杂性,除非您对其中的集合进行任何循环,而您不会这样做。


答案 2

你应该在 API 中找到它:n log(n)。