Ma mise en oeuvre du tri d'insertion

Question

Voici ma mise en oeuvre du tri d'insertion en java pour une liste doublement chaînée. J'ai vérifié de nombreuses valeurs et cela me donne une sortie correcte. Ma question est:

1. Je ne sais pas comment calculer le temps de l'algorithme pour cela, je veux dire O (n)
2. peut-il être optimisé? Quelqu'un peut-il pointer vers un code qui est plus optimisé?

Nota: Le code utilise ganglion sentinelle pour que les points au début de la liste chaînée-à-dire sentinelle node.next à des points de départ noeud de liste, et point de node.PREV sentinelle au dernier noeud de la liste des points liés et la tête au noeud sentinelle .

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

c'est O (N^2), car 1 boucle imbriquée. et tous les 2 boucles parcourent toute la liste