1

現在、私はアルゴリズムに関する本を読んでいて、このソートの使用法を見つけました。

元の順序の再構築-いくつかのアプリケーションのためにそれらを並べ替えた後、どのようにアイテムのセットの元の配置を復元できますか？i番目のレコードがこのフィールドをiに設定するように、アイテムのデータレコードにフィールドを追加します。レコードを移動するときはいつでもこのフィールドを持ち歩き、後で最初の注文を元に戻したいときに並べ替えます。

私はそれが何を意味するのかを理解しようと懸命に努力してきました。そして、私は惨めに失敗しました。誰か助けてくれませんか？

4

3 に答える 3

5

ランダムな順序でアイテムのリストがあるとします。

itemC, itemB, itemA, itemD

あなたはそれらを分類しました：

itemA, itemB, itemC, itemD

また、それらを別の場所に保存するのに十分なメモリがなかったため、元のシーケンスが失われます。さらに、元の順序はランダムであり、復元するのは問題があり、不可能です。

この記事では、この問題の解決策を示します。

i番目のレコードがこのフィールドをiに設定するように、アイテムのデータレコードにフィールドを追加します

そのため、アイテムごとにフィールドを追加します。

(itemC,1), (itemB,2), (itemA,3), (itemD, 4)

そして、ソート後、次のようになります。

(itemA,3), (itemB,2), (itemC,1), (itemD, 4)

したがって、追加フィールドによる最初の順序の並べ替えを簡単に復元できます

于 2013-03-01T10:39:02.487 に答える
3

配列にデータがあるとしましょう。これは、例として使用できる最も単純な構造だからです。

したがって、ノード（つまり、配列の要素）は次のようになります。

 (some data type) data

アルゴリズムは整数フィールドを追加することを提案しているので、次のようになります。

 (some data type) data,
 int              position

次に、実際のインデックスで位置を埋めます。この擬似コードのようなもの：

for current: 0 to lastElement
  array[current].position = current

（それは私が知っているどの言語でも書かれていませんが、読めるはずです）

それを行った後、必要に応じてシャッフル（リゾート）します。

元の順序を復元する場合は、positionフィールドで並べ替えるだけです。

于 2013-03-01T10:34:47.740 に答える
1

さて、基本的には、元の順序（順列によって破壊される）を追跡するために何らかのものが必要であると言っています。1つのオプションは、順列を単純に逆にすることです（Steve Jessopの有益な回答をここで確認してください）。

順列を反転する別のオプションでは、必要な処理ステップは少なくなりますが、メモリは多くなります。より具体的には、入力セットの各ノードには追加のIDフィールドがあり、この入力セットのすべての要素はこのフィールドに基づいて並べ替えられます。順列を適用すると、IDがソートされた順序ではなくなったことは明らかです。順列を反転したい場合は、このフィールドに基づいてリストを再度並べ替えるだけです。

于 2013-03-01T10:41:17.773 に答える