1

次のデータセットがリンクリストに保存されているとします (ヘッダーを除く)。

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

ここで、たとえばアルファベット順にノードを並べ替えたいと思います。

配列 (および Lists、Vectors、ArrayLists などの同様のもの) を使用せずに、ライブラリの並べ替え方法 (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;
    }
}
4

5 に答える 5

2

自分でやりたい場合は、リンクされたリストでの挿入ソートは非常に簡単です。新しい空のリンク リストを作成し、古いリストのすべての要素をそこに挿入します。ウィキペディアには C コードの 例があります。

于 2012-12-30T15:31:59.050 に答える
1

Collections.sortを使用したくないとおっしゃっていますが、念のために言っておきますが、Collections.sortを使用すると、並べ替え順序を自分で実装できることをご存知ですか？そうでない場合は、http：//www.digizol.com/2008/07/java-sorting-comparator-vs-comparable.html（および他の多くのリソース）がその情報を提供します。

それ以外の場合は、実装できる並べ替えアルゴリズムがたくさんあります。理解しやすいものの1つは、バブルソートです。http://en.wikipedia.org/wiki/Bubble_sortには、さまざまな並べ替え手順の優れた視覚化など、その説明が含まれています。

しかし、バブルソートは（まったく）効率的なソート方法ではありません。他にも多くのソートアルゴリズム（マージソート、挿入ソート、クイックソートなど）があり、概要についてはWikipediaの「ソートアルゴリズム」の記事を参照してください。それぞれに長所と短所があります。並べ替えるデータによって、どのアルゴリズムが最適かが異なります。

于 2012-12-30T15:42:00.053 に答える
1

JDK がどのように機能するかを知りたい場合は、リストを配列にコピーし、それを並べ替えて、元に戻します。

リンクされたリストにバブルソートを使用できますが、遅くなるため、苦痛が好きでない限り意味がありません。;)

于 2012-12-30T15:28:25.660 に答える
0

リストを配列にコピーして並べ替えることができます。それ以外の場合は、マージ ソート、バブル ソートなど、さまざまなソート アルゴリズムを使用できます。

これは、マージソートの実装で確認できます。

于 2012-12-30T15:30:04.567 に答える
0

まったく同じではありませんが、外部ソート (データがメモリにロードされない場合。たとえば、RAM よりも大きなファイルをソートしたい場合) を見てください。それらは通常、リンクされたリスト間でノードを移動する方法と同様の方法で、ファイル間でデータを移動することによって機能します。

于 2012-12-30T15:36:29.247 に答える