-2

LinkedList並べ替える必要のあるものがあり（ intsが含まれています）、その方法がわかりません。誰かが私のソースコードを与えてintリンクリストをソートできますか？

オンラインで見つけたこのコードを試しましたが、機能しませんでした。

    public void sort(LinkedList sortlist)
{
    //Enter loop only if there are elements in list
    boolean swapped = (head != null);

    // Only continue loop if a swap is made
    while (swapped)
    {
        swapped = false;

        // Maintain pointers
        Node curr = head;
        Node next = curr.link;
        Node prev = null;

        // Cannot swap last element with its next
        while (next != null)
        {
            // swap if items in wrong order
            if (curr.data>next.data)
            {
                // notify loop to do one more pass
                swapped = true;

                // swap elements (swapping head in special case
                if (curr == head)
                {
                    head = next;
                    Node temp = next.link;
                    next.link = curr;
                    curr.link = temp;
                    curr = head;
                }
                else
                {
                    prev.link = curr.link;
                    curr.link = next.link;
                    next.link = curr;
                    curr = next;
                }
            }

            // move to next element
            prev = curr;
            curr = curr.link;
            next = curr.link;
        }
    }
}
4

2 に答える 2

3

スタンフォードのCS106Bコースのこのハンドアウトに記載されているリンクリストには、マージソートのC++実装があります。時間O（n log n）で実行されますが、これは非常に優れています。

他のアプローチの調査については、リンクリストを並べ替える方法に関するこの古いSOの回答を確認してください。そこにはコードはありませんが、既存のアイデアをリンクリストで機能するように適応させる方法についての適切な説明があります。

お役に立てれば！

于 2013-01-11T03:25:55.993 に答える
0

マージソートとクイックソートを使用して、llink-lists（平均O（n.long））を適切にソートできます。さらに、数値が整数の場合、O（n）で機能する基数ソートのバリエーションがあり、適切に配置されます。したがって、リンクリストを配列に変換するために会うことはありません。

STLでの実装に関する情報は次のとおりです。http ：//www.cplusplus.com/reference/list/list/sort/

于 2013-02-02T07:32:32.117 に答える