Sorting Array，Sorting ArrayList，using Collections

好的，仍在學習數組。我寫了這個代碼，填充名爲「rand」的數組，其中0和1之間的隨機數（獨佔）。我想開始學習複雜性。 For循環執行n次（100次），每次需要O（1）次，所以最壞的情況是O（n），對嗎？此外，我用ArrayList來存儲100個元素，我導入了「Collections」，並使用Collections.sort（）方法對元素進行排序。Sorting Array，Sorting ArrayList，using Collections

import java.util.Arrays; 
    public class random 
    { 
     public static void main(String args[]) 
     { 
      double[] rand=new double[10]; 

        for(int i=0;i<rand.length;i++) 
        { 
         rand[i]=(double) Math.random(); 
         System.out.println(rand[i]); 
        } 

        Arrays.sort(rand); 
        System.out.println(Arrays.toString(rand)); 
     } 
    }

的ArrayList：

import java.util.ArrayList; 
import java.util.Collections; 

public class random 
{ 
    public static void main(String args[]) 
    { 
     ArrayList<Double> MyArrayList=new ArrayList<Double>(); 


     for(int i=0;i<100;i++) 
     {    
      MyArrayList.add(Math.random()); 
     } 

     Collections.sort(MyArrayList); 


     for(int j=0;j<MyArrayList.size();j++) 
     { 
      System.out.println(MyArrayList.get(j)); 
     } 

    } 
}

來源

2012-09-01 user1639637

那麼你的問題是什麼？ – Tudor

是的，你是正確的，添加N項目的複雜度爲O（N）。在大多數情況下，根據該文檔排序將額外需要O（N *日誌（N））：

排序算法是一個調諧快速排序，改編自喬恩L. 本特利和M.道格拉斯麥克羅伊的「工程一個排序功能「，軟件 - 實踐和經驗，卷。 23（11）第1249-1265頁（November 1993）。該算法在許多數據集上提供n * log（n）性能，導致其他快速排序降級爲二次性能。

ArrayList仍然是一個數組的支持，所以複雜性將是相同的，因此，無論如何，偶爾會調整大小。

來源

2012-09-01 15:48:46 Tudor

Sorting Array，Sorting ArrayList，using Collections

回答

相關問題