Почему этот код работает неправильно для сортировки связанного списка с использованием сортировки пузырьков?

Question

Я реализовал сортировку пузыря, используя LinkedList следующим образом. Я не могу найти правильное и эффективное решение этой проблемы. Какие изменения необходимы в этом коде, чтобы обеспечить эффективность работы. Если кто-то имеет лучшую и эффективную реализацию сортировки пузыря по связанным списком, пожалуйста, предоставьте это.

class SortList { 
    int size; 
    Node head; 
    class Node{ 
    int data; 

    Node next; 
    Node(int data){ 
     this.data = data; 
     this.next = null; 
     } 
    Node(){ 
     this.data = 0; 
     this.next = null; 
    } 
    } 

    public void push(int d) { 
     Node newNode = new Node(); 

     newNode.data = d; 

     newNode.next = head; 

     head = newNode; 
     size++; 
    } 
    public void display(){ 
    Node n = head; 
    while(n!=null){ 
     System.out.print(n.data +" "); 

     n = n.next; 
     } 
    } 
    public int getLength(){ 
     int count=0; 
     Node n = head; 
     while(n!=null){ 
      count++; 
      n = n.next; 
      } 
      return count; 
    } 
    public int getLengthR(Node n){ 

      if(n==null) return 0; 
      return 1+getLengthR(n.next); 

    } 
    public int getL(){ 
    return getLengthR(head); 
    } 
    public static void main(String[] args) { 
     SortList ls = new SortList(); 
    int[]arrList = {5,2,7,3,1,2}; 
    for(int i=0;i<arrList.length;i++){ 
     ls.push(arrList[i]); 
     } 
     ls.display(); 

     ls.sortList(); 

     ls.display(); 
    } 

    public void sortList(){ 
    if(size > 1){ 
     Node node = head; 
     Node nextNode = head.next; 
      for(int i=0;i<size;i++){ 

      for(int j=0;j<size - i - 1;j++){ 
       while(node.data > nextNode.data){ 
        Node temp =node; 
        node = nextNode; 
        nextNode = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
     } 

     } 
    } 
} 

Answer 1

Возможно, вы должны рассмотреть ответ StackOverFlow, предложенный в комментариях. Я изменил ваш метод сортировки, используя немного другую тактику. Вместо того, чтобы обменивать узлы, я менял местами значения в узлах. Это может не всегда применяться, поскольку могут быть другие данные, которые связаны с узлами, которые вы не используете для сортировки, которые также могут быть заменены.

В основном подход, приведенный ниже, заключается в уменьшении размера списка на один после каждого прохода. Это делается путем отслеживания узла, который был просто помещен в правильное положение, используя переменную terminal.

public void sortList(){ 
    if(size > 1){ 
     Node terminal = null; 
     while (head.next != terminal) { 
      Node node = head; 
      Node nextNode = head.next; 

      while (nextNode != terminal) { 
       if(node.data > nextNode.data){ 
        int temp =node.data; 
        node.data = nextNode.data; 
        nextNode.data = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
      terminal = node; 
     } 
    } 
}