排序鏈接列表實現

Question

我想在我的自定義鏈接列表中實現排序方法。我正在嘗試使用冒泡排序，但不知道如何去做。

class Node { 
    int data; 
    Node next; 

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

    public int getData() { 
     return data; 
    } 

    public void setData(int data) { 
     this.data = data; 
    } 

    public Node getNext() { 
     return next; 
    } 

    public void setNext(Node next) { 
     this.next = next; 
    } 
} 

public class LinkedList { 
    private Node head; 

    public LinkedList() { 
     this.head = null; 
    } 

    public void insert(int data) { 
     Node node = new Node(data); 
     if (head == null) { 
      head = node; 
     } else { 
      Node temp = head; 

      while (temp.getNext() != null) { 
       temp = temp.getNext(); 
      } 
      temp.setNext(node); 
     } 
    } 

    public void reverse() { 
     Node temp = head; 
     Node back = null; 

     while (temp != null) { 
      Node next = temp.getNext(); 
      temp.setNext(back); 
      back = temp; 
      temp = next; 
     } 
     head = back; 
    } 

    public void print() { 
     Node temp = head; 
     while (temp != null) { 
      System.out.print(temp.getData() + " -- > "); 
      temp = temp.getNext(); 
     } 
    } 

    public void sort() { 
     // Bubble sort (but i am lost) 
     Node outer = head; 
     while(outer != null){   
      Node inner = head;   
      while(inner != null){ 
       // TODO 
      }   
      outer = outer.getNext(); 
     }  
    } 
} 

Answer 1

你應該從Wikipedia採取了這種僞代碼開始：

procedure bubbleSort(A : list of sortable items) 
    n = length(A) 
    repeat  
    swapped = false 
    for i = 1 to n-1 inclusive do 
     /* if this pair is out of order */ 
     if A[i-1] > A[i] then 
     /* swap them and remember something changed */ 
     swap(A[i-1], A[i]) 
     swapped = true 
     end if 
    end for 
    until not swapped 
end procedure 

如果能夠交換（I-1）和第i個元素，你應該能夠寫整個事情（因爲你知道如何瀏覽你的鏈表）。