Java 中的 collection.sort() 函数有多快?使用了什么算法?我遇到了这个功能 in this answer按降序对列表进行排序:
public static void main(String arg[])
{
List<Double> testList=new ArrayList();
/*Adding The values to the List*/
testList.add(0.5);
testList.add(0.2);
testList.add(0.9);
testList.add(0.1);
testList.add(0.1);
testList.add(0.1);
testList.add(0.54);
testList.add(0.71);
testList.add(0.71);
testList.add(0.71);
testList.add(0.92);
testList.add(0.12);
testList.add(0.65);
testList.add(0.34);
testList.add(0.62);
/*Declare a new List for storing sorted Results*/
List<Double> finalList=new ArrayList();
while(!testList.isEmpty()) //perform operation until all elements are moved to new List
{
double rank=0;
int i=0;
for(double d: testList)
{
if(d>=rank)
{
rank=d;
}
}
finalList.add(rank);
testList.remove(testList.indexOf(rank));
}
for(double d : finalList) {
System.out.println(d);
}
}
我认为这在 O(n(n-1)) 时间内运行,对于大型列表来说效率很低。考虑到 Collections.sort() 的效率低下,我不相信这是创建它的方式。
最佳答案
来自集合的方法 sort() 的文档:
Implementation note: This implementation is a stable, adaptive, iterative
mergesort
that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays.
这意味着 O(n log n) 在最坏的情况下。所以是的,它非常快(即使在最坏的情况下),比 O(n^2) 排序算法快得多。
关于java - collection.sort() 函数的效率如何?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26088567/