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

從館藏的方法排序（）文檔：

實現注意事項：這個實現是一個穩定的，自適應的，迭代mergesort需要遠遠大於n LG較少（n）的比較，當輸入數組部分排序，同時在輸入數組隨機排序時提供傳統合並排序的性能。如果輸入數組接近排序，則實現需要大約n次比較。臨時存儲要求從幾乎排序的輸入數組的小常量到隨機排序的輸入數組的n/2個對象引用。

這意味着是中的O 最壞的情況下（N log n）的。因此，它的速度非常快（甚至在最壞的情況下），比O（n^2）排序算法快得多。

Answer 2

引述the documentation：

實現注意事項：此實現了穩定的，自適應的，迭代的歸併需要遠小於n LG更少（n）的比較，當輸入陣列部分地排序，同時還提供了性能當輸入數組是隨機排序的時候，傳統的合併排序。如果輸入數組幾乎排序，則實現需要大約n次比較。臨時存儲要求從幾乎排序的輸入數組的小常量到隨機排序的輸入數組的n/2個對象引用。

該實現在其輸入數組中具有升序和降序的相等優勢，並且可以利用相同輸入數組的不同部分的升序和降序。它非常適合合併兩個或多個有序數組：簡單地連接數組並對結果數組進行排序。

該實現改編自Tim Peters的Python列表排序（TimSort）。它使用Peter McIlroy的「Optimistic Sorting and Information Theoretic Complexity」中的技術，在Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms，第467-474頁，1993年1月。

該實現將指定列表轉儲到數組，對數組進行排序，然後迭代列表，重置數組中相應位置的每個元素。這樣可以避免因試圖對鏈表進行排序而導致的n2 log（n）性能。