排序链表

Question

假设我有以下数据集存储在一个链表中(不包括头):

ID | Name
1 | John
2 | Albert
3 | Simon

现在，我想按照字母顺序对节点进行排序。

我想知道如何在不使用数组(和类似的东西，如列表，向量，数组列表等)和不使用库排序方法(例如Collections.sort)的情况下提出我自己的排序方法。

换句话说，我想知道排序的概念，以及如何以系统的方式安排节点。它不需要是高效的——它只需要工作。

我将在Java中尝试这一点，但我也会感谢伪代码或提示/提示/其他资源。

谢谢。

---

附录:

LinkedList.java

class LinkedList
{
    private Node head;  // first node in the linked list
    private int count;
    public int getCount()
    {
        return count;
    }
    public Node getHead()
    {
        return head;
    }
    public LinkedList()
    {
        head = null;    // creates an empty linked list
        count = 0;
    }
    public void deleteFromFront()
    {
        if (count > 0)
        {
            Node temp = head;
            head = temp.getLink();
            temp = null;
            count--;
        }
    }
    public void AddToFront(Object cd)
    {
        Node newNode = new Node(cd);
        newNode.setLink(head);
        head = newNode;
        count++;
    }
    public void RemoveAtPosition(int n)
    {
        int counter=1;
        Node previous=null;
        if(n==1)
            deleteFromFront();
        else if(n<=getCount())
            for(Node j=head;j!=null;j=j.getLink())
            {
                if(counter==n&&previous!=null)
                {
                    previous.setLink(j.getLink());
                    j.setLink(null);
                }
                previous=j;
                counter++;
            }
        else
            System.out.println("Unable to remove object at position "+n);
    }
    public void AddAtPosition(int n, Object cd)
    {
        int counter=1;
        Node newNode=new Node(cd);
        Node previous=null;
        for(Node j=head;j!=null;j=j.getLink())
        {
            if(counter==n&&previous!=null)
            {
                newNode.setLink(j.getLink());
                j.setLink(newNode);
            }
            previous=j;
            counter++;
        }
    }
    public void Swap(int n1, int n2)
    {
        // how do I swap nodes?
    }
    public void Sort()
    {
       // how do I sort nodes?
    }
}

Node.java

public class Node {
    private Object data;
    private Node link;
    public Object getData() {
        return data;
    }
    public void setData(Object data) {
        this.data = data;
    }
    public Node getLink() {
        return link;
    }
    public void setLink(Node link) {
        this.link = link;
    }
    public Node(Object data) {
        this.data = data;
        this.link = null;
    }
}

Answer 1

如果你想自己做，插入排序在链表上非常容易。创建一个新的空链表，然后将旧链表中的所有元素插入其中。Wikipedia有一个C代码示例

Answer 2

如果你想知道JDK是如何做到的…I将列表复制到一个数组中，排序后再复制回来。

你可以对链表使用冒泡排序，但它会比较慢，所以它没有意义，除非你喜欢痛苦。div;)

我知道你说你不想使用集合。排序，但只是为了确保:你确实意识到集合。Sort允许你自己实现排序顺序，对吧?如果没有，http://www.digizol.com/2008/07/java-sorting-comparator-vs-comparable.html(和许多其他资源)将提供相关信息。

否则，有很多排序算法可以实现。其中比较容易理解的是冒泡排序。http://en.wikipedia.org/wiki/Bubble_sort有一个很好的解释，包括不同排序步骤的可视化。

但是冒泡排序并不是一种有效的排序方式。还有许多其他排序算法(归并排序、插入排序、快速排序……有关概述，请参阅Wikipedia关于"排序算法"的文章)，它们各有优缺点。这取决于你要排序的数据哪种算法最适合。

您可以将列表复制到数组中并对其进行排序。否则，有各种排序算法可以使用，如归并排序，冒泡排序等。

您可以在合并排序实现中看到这个

虽然不完全相同，但看看外部排序(其中数据不加载到内存中;例如，您希望对大于RAM的文件进行排序)。它们通常通过在文件之间移动数据来工作，其方式类似于在链表之间移动节点。