排序链表实现

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 个元素，你应该能够写出整个东西（因为你知道如何浏览链表）。

排序链表实现

Sort Linked List implementation

java

linked-list

data-structures