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

Question

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() 的效率低下，我不相信这是创建它的方式。

Answer 1

来自集合的方法 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) 排序算法快得多。