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


问题内容

我写了以下课程:

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”和“ angle”字段的对象。

然后,我使用:

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

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


问题答案:

您可能已经阅读了有关Collections排序的文档,但是这里适合您:

排序算法是一种修改的mergesort(如果低子列表中的最高元素小于高子列表中的最低元素,则忽略合并)。该算法提供了有保证的n log(n)性能。

比较器不会改变这种复杂性,除非您对集合中的循环执行任何操作,否则您不会这样做。