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());
这种排序方法的复杂性是多少？
I have written the following class:
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;
}
}
Then, in my main() method, I have created a List to which I add some objects which has "X" and "angle" field.
I then use:
Collections.sort(list, new SortingObjectsWithAngleField());
What is the complexity of this sort method?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以阅读有关集合排序的文档，但这里适合您：
您的比较器不会改变这种复杂性，除非您对其中的集合进行循环操作，而您却没有这样做。
You could have read up the docs on Collections sort, but here it is for you:
Your Comparator doesn't change this complexity, unless you do anything with loops over your collection in it, which you don't.
您应该在 API 中找到它： n log(n)。
You should have found it in the API: n log(n).
摘自 Collections.sort -
Taken from Collections.sort -
每个人都说过 API doc，添加了一些我找到的更相关的信息。
如果您提供自定义比较器，则会使用合并排序的修改版本（也称为
timsort）。该实现借用自python 列表排序。在最好的情况下，只需要 n-1 次比较，因此
最好的情况是 O(n)并且在所有情况下保证性能是 O(n.lg(n))< /代码>Everyone has stated the API doc, adding some more relevant information which I found.
If you provide custom comparator, then a modified version of mergesort (also known as
timsort) is used. The implementation has been borrowed from list sort for python.In the best case as few as n-1 comparisons are needed, so
best case is O(n)andguaranteed performance in all the cases is O(n.lg(n))