1

単一リンクリストがあり、メモリの制限のために一定のスペースで並べ替える必要があります（つまり、リスト内のアイテムの数に比例する余分なスペースを使用しないでください）。

リンクリストの構造は次のとおりです。

  • head.item=並べ替えるペイロード; と
  • head.next=次のアイテム。

別のリストを作成する場合の一定のスペース割引ソリューションの要件は、その場で行う必要があります。

どうやってやるの？

4

3 に答える 3

12

リンクされたリストを定数空間でソートするのは簡単です。ポインターを調整するだけです。これを行う最も簡単な方法は、隣接する要素のみを交換する並べ替えアルゴリズムを使用することです。効率性を要求していないという理由だけで、バブルソートを提供します。

# Enter loop only if there are elements in list.

swapped = (head <> null)
while swapped:
    # Only continue loop if a swap is made.

    swapped = false

    # Maintain pointers.

    curr = head
    next = curr.next
    prev = null

    # Cannot swap last element with its next.

    while next <> null:
        # Swap if items in wrong order.

        if curr.item > next.item:
            # Notify loop to do one more pass.

            swapped = true

            # Swap elements (swapping head is special case).

            if curr == head:
                head = next
                temp = next.next
                next.next = curr
                curr.next = temp
                curr = head
            else:
                prev.next = curr.next
                curr.next = next.next
                next.next = curr
                curr = next
            endif
        endif

        # Move to next element.

        prev = curr
        curr = curr.next
        next = curr.next
    endwhile
endwhile
于 2009-05-09T01:11:21.020 に答える
1

いくつかの方法：

  • 所定の場所にあるリストでバブルソートを使用します。リストが小さい場合、これは十分に高速である必要があります
  • リストを配列にコピーし、ヒープソートまたはクイックソートを使用してからコピーし直します
  • リストのbogosortを適切に使用します。最良の場合の複雑さはO(n)、非常に高速である必要があるためです*

*予想される実行時の複雑さはO(n*n!)

于 2009-05-09T00:55:31.260 に答える
1

リンクされたリストのインプレース ソートについては、マージ ソートをお勧めします。安定しており、NlgN 時間で実行されます。

于 2011-02-05T21:31:32.880 に答える