collection.sort()函数的效率如何？

Question

Java中的collection.sort()函数有多快？使用了什么算法？我在这个答案中遇到了这个函数,它按降序对列表进行排序:

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()的创建方式,考虑到效率低下.

Answer 1

从Collection的方法sort()上的文档:

实现注意事项:此实现是一种稳定的自适应迭代mergesort,当输入数组被部分排序时,需要远低于n lg(n)的比较,同时在输入数组随机排序时提供传统mergesort的性能.如果输入数组几乎已排序,则实现需要大约n次比较.临时存储要求从几乎排序的输入数组的小常量到随机排序的输入数组的n/2个对象引用不等.

这意味着在最坏的情况下是O(n log n).因此,它非常快(即使在最坏的情况下),比O(n ^ 2)排序算法快得多.