de comptage dans inversions une liste liée à O (n log n) en cours d'exécution

Question

J'ai créé une liste chaînée très simple en Java:

public class LinkedList { 
    class Node { 
     public Node next; 
     public int item; 

     public Node (int item) { 
      this.item = item; 
     } 
    } 

    int listSize = 0; 
    Node first = null; 
    Node last = null; 

    public void add(int n) { 
     Node node = new Node(n); 
     if (first == null) { 
      first = node; 
     } else { 
      last.next = node; 
     } 
     last = node; 
     listSize++; 
    } 
} 

Ainsi, dans la classe principale, je vais ajouter des éléments à la liste liée dans un ordre aléatoire. Mais comment puis-je créer une méthode qui compte le nombre d'inversions dans la liste liée?

Jusqu'à présent, je suis parvenu à le réaliser avec O (N^2) durée:

public int inversionCount() { 
     int count = 0; 
     Node current = this.first; 
     for (int i = 0; i <= this.listSize - 2; i++) { 
      Node next = current.next; 
      for (int j = i + 1; j < this.listSize; j++) { 
       if (current.item > next.item) { 
        System.out.print("(" + current.item + "," + next.item + ")" + " "); 
        count += 1; 
       } 
       next = next.next; 
      } 
      current = current.next; 
     } 
     return count; 
    } 

Cependant, comme je l'ai dit, le temps d'exécution pour cet algorithme est O (N^2) . J'essaie d'atteindre un temps de fonctionnement de O (NlogN). Comment cela peut il etre accompli?

Answer 1

Vous utilisez bulle genre qui a la complexité de O (n^2)

Pour liste chaînée l'algorithme qui est applicable à la complexité de O (n log n) est Fusion Trier.

S'il vous plaît voir this walk trough of merge sort for linked lists