1

假设我将以下数据集存储在链表中（不包括标题）：

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

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

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

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

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

谢谢你。

附录：

链表.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?
    }
}

节点.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;
    }
}
4

5 回答 5

2

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

于 2012-12-30T15:31:59.050 回答
1

如果您想知道 JDK 是如何做到的……我将列表复制到一个数组中，对其进行排序并将其复制回来。

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

于 2012-12-30T15:28:25.660 回答
1

我知道您说您不想使用 Collections.sort，但只是为了确保：您确实意识到 Collections.sort 允许您自己实现排序顺序，对吗？如果没有，http://www.digizol.com/2008/07/java-sorting-comparator-vs-comparable.html（以及许多其他资源）将提供有关信息。

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

但是冒泡排序（根本不是）一种有效的排序方式。还有许多其他的排序算法（合并排序、插入排序、快速排序……请参阅维基百科关于“排序算法”的文章以获得概述），它们各有优缺点。这取决于您要排序的数据，哪种算法最适合。

于 2012-12-30T15:42:00.053 回答
0

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

您可以在合并排序实现中看到这一点。

于 2012-12-30T15:30:04.567 回答
0

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

于 2012-12-30T15:36:29.247 回答