java.util.Collections.sort() 方法的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4254122/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the time complexity of java.util.Collections.sort() method?
提问by user472221
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 Listto which I add some objects which has "X" and "angle" field.
然后，在我的main()方法中，我创建了一个，List向其中添加了一些具有“X”和“角度”字段的对象。
I then use:
然后我使用：
Collections.sort(list, new SortingObjectsWithAngleField());
What is the complexity of this sort method?
这种排序方法的复杂性是什么？
采纳答案by Jan Thom?
You could have read up the docs on Collections sort, but here it is for you:
您可以阅读有关集合排序的文档，但这里是为您准备的：
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.
排序算法是一种改进的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。该算法提供有保证的 n log(n) 性能。
Your Comparator doesn't change this complexity, unless you do anything with loops over your collection in it, which you don't.
您的 Comparator 不会改变这种复杂性，除非您对其中的集合执行任何循环，而您没有这样做。
回答by LiorH
Taken from Collections.sort -
取自 Collections.sort -
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
排序算法是一种改进的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）。该算法提供有保证的 n*log(n) 性能
回答by avp
Everyone has stated the API doc, adding some more relevant information which I found.
每个人都声明了API 文档，并添加了一些我发现的相关信息。
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.
如果您提供自定义比较器，则使用合并排序的修改版本（也称为timsort）。该实现是从list sort for python 中借用的。
In the best case as few as n-1 comparisons are needed, so best case is O(n)and guaranteed performance in all the cases is O(n.lg(n))
在最好的情况下，只需要 n-1 次比较，所以best case is O(n)和guaranteed performance in all the cases is O(n.lg(n))
