私の挿入の並べ替えの実装

Question

これは、二重リンクされたリストのJavaでの挿入の並べ替えの私の実装です。私は多くの値をチェックして、それは私に正しい出力を与える。私の質問は次のとおりです。

1. 私はO（n）を意味し、このためのアルゴリズムの時間を計算する方法がわからない
2. これを最適化することができますか？誰かがより最適化されたコードを指すことができますか？

注：それはリンクリストの先頭を指すようにコードは、センチネルリンパ節を使用していますすなわちセンチネルnode.nextノードをセンチネルにリンクされているリストとヘッドポイントの最後のノードにリンクされているリストとセンチネルnode.PREVポイントのノードを開始するポイント。

public void sortInsertionAsce(){ 
      DListNode marker,aheadOfCurrent;; 
      DListNode current = head.getNext(); 
      aheadOfCurrent = current.getNext(); 
      marker=current; 
      while(aheadOfCurrent.getNext()!=current){ 
      if(marker.getItem()>aheadOfCurrent.getItem()){ 
       swap(aheadOfCurrent,marker); 
       marker=aheadOfCurrent; 
        while(aheadOfCurrent.getPrev()!=current){ 
         aheadOfCurrent=aheadOfCurrent.getPrev(); 
         if(aheadOfCurrent.getPrev().getItem()>aheadOfCurrent.getItem()){ 
          swap(aheadOfCurrent.getPrev(),aheadOfCurrent); 
         } 
        } 
        aheadOfCurrent=marker; 
       } 
        marker=aheadOfCurrent; 
        aheadOfCurrent=aheadOfCurrent.getNext(); 
      } 
     } 

Answer 1

これは、O（N^2）、beacause 1のネストループです。すべての2つのループがすべてのリストを反復する