如何对一组链接节点进行排序

Question

我正在尝试在java中对一组链接节点进行排序。我刚开始编程，所以我不确定我做错了什么。

package rAymond;
public class RandomLinkLists {
    public static void main(String[] args) {
        int temp = 0;
        Listnode holder;
        Listnode start;
        Listnode a;
        Listnode b;
        Listnode c;
        Listnode d;
        Listnode e;
        Listnode end;
        start = new Listnode(5);
        a = new Listnode(10);
        b = new Listnode(0);
        c = new Listnode(3);
        d = new Listnode(4);
        e = new Listnode(100);
        end = new Listnode(20);
        holder = new Listnode(0);
        start.setNext(a);
        a.setNext(b);
        b.setNext(c);
        c.setNext(d);
        d.setNext(e);
        e.setNext(end);
        holder.setNext(start);
        while(start!=null && start.getNext()!=null){
            if((Integer)start.getData() > (Integer)start.getNext().getData()){
                temp = (Integer) start.getData();
                start.setData(start.getNext().getData());
                start.getNext().setData(temp);
            }
            start = start.getNext();
        }
        while(holder != null &&  holder.getNext()!=null){
            System.out.println(holder.getData());
            holder = holder.getNext();
        }
    }
}

和。。。

package rAymond;
public class Listnode {
  //*** fields ***
    private Object data;
    private Listnode next;
    private Listnode previous;
  //*** methods ***
    // 2 constructors
    public Listnode(Object d) {
    this(d, null);
    }
    public Listnode(Object d, Listnode n) {
    data = d;
    next = n;
    }
    // access to fields
    public Object getData() {
        return data;
    }
    public Listnode getPrevious(){
        return previous;
    }
    public Listnode getNext() {
        return next;
    }
    // modify fields
    public void setData(Object ob) {
        data = ob;
    }
    public void setNext(Listnode n) {
        next = n;
    }
    public void setPrevious(Listnode n) {
        previous = n;
    }
    public void remove(Listnode current, Listnode parent){
        parent.setNext(current.getNext());
    }
}

任何帮助将不胜感激。

最终输出为：0 5 0 3 4 10 20

另外，有没有更简单的方法来对列表进行排序？这里的气泡排序和快速排序等普通数组排序技术可以应用吗？

Answer 1

面向随机访问的排序算法对于链表来说很尴尬。一个简单的方法是创建一个空列表，然后从原始列表中删除节点并按顺序将它们插入到初始空列表中。

一种更快的方法是使用一小数组引用（或指向节点的指针）和自下而上的合并排序的变体。维基文章：

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists