java - 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

您可能已经阅读了有关集合排序的文档，但这里是为您准备的:

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance.

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