java.util.Collections.sort（）方法的时间复杂度是多少？ [英] What is the time complexity of java.util.Collections.sort() method?

问题描述

我编写了以下类：

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字段的对象。

Then, in my main() method, I have created a List to which I add some objects which has "X" and "angle" field.

然后我使用：

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

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

What is the complexity of this sort method?

推荐答案

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

You could have read up the docs on Collections sort, but here it is for you:

排序算法是一个修改过的
mergesort（如果
low子列表中的最高元素小于高b中的最低
元素，则合并为
省略子表）。这个
算法可以保证n log（n）
的性能。

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.

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

Your Comparator doesn't change this complexity, unless you do anything with loops over your collection in it, which you don't.

这篇关于java.util.Collections.sort（）方法的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！