1

以下のように、C++RobertSedwickによるアルゴリズムの多次元ソートについて読んでいます。

多次元ソートを処理するには、ソートキーがベクトルであり、キーの最初のコンポーネントが順番になるようにレコードが再配置され、次に最初のコンポーネントが等しいものが2番目のコンポーネントの順に並べられます。コンポーネントに重複するkdeysがない場合、問題は最初のコンポーネントでのソートに限定されます。ただし、一般的なアプリケーションでは、各コンポーネントにいくつかの異なる値しかなく、3方向のパーティション分割（中間パーティションの次のコンポーネントに移動する）があります。

上記のテキストに関する私の質問は

  1. 著者は、最初のコンポーネント、2番目のコンポーネントとはどういう意味ですか？
  2. コンポーネントに重複キーがない場合、作成者は、問題が最初のコンポーネントでの並べ替えに還元されるとはどういう意味ですか？

お時間を割いていただきありがとうございます

4

3 に答える 3

2

著者は、マッピング内のキーの辞書式順序について説明しています。値のペアのリストがあると想像してください。

(4 3), (2 3), (1 4), (4 2)

各ペアの最初のコンポーネントは「最初のコンポーネント」と呼ばれ、2番目のコンポーネントはもちろん「2番目のコンポーネント」と呼ばれます。これらのアイテムの辞書式順序は次のとおりです。

(1 4), (2 3), (4 2), (4 3)

どうやってこれにたどり着くのですか？最初に、ペアは最初のコンポーネントでソートされます。最初のコンポーネントは4, 2, 1, 4、順番にです1, 2, 4, 4。しかし、2つの4があります。(4 2)さらに、の前に来るような2番目のコンポーネントでそれらを注文できます(4 3)。

もちろん、ペアである必要はありません。任意の数の値を持つ要素に辞書式順序を適用できます。それらは、最初のコンポーネント、次に2番目、次に3番目というように順序付けられます。

この順序付けの名前は、多くの言語で単語を順序付ける方法に由来しています。ジョン、ジム、アリスの3つの名前が与えられた場合、どのように注文しますか？最初に最初の文字で注文し、次に2番目の文字で注文します。これらの名前の辞書式順序は、Alice、Jim、Johnです。

著者の説明では、この種の順序付けは、マップのキーを順序付けるために使用されています。つまり、ペアはある値にマップされます。たとえば、キーがペアで、値が文字である場合があります。

(4 3) => A, (2 3) => B, (1 4) => C, (4 2) => D

キーを辞書式にソートした後のこれらの文字の順序は、になりますC, B, D, A。

于 2012-11-27T13:58:19.560 に答える
1

著者は、最初のコンポーネント、2番目のコンポーネントとはどういう意味ですか？

配列の最初、2番目の要素。これは次のとおりです。intarr1[]= {1,2,3,4}、arr2 [] = {5,6,7,8} arr1の最初のコンポーネントは1で、arr2の最初のコンポーネントは5です。

コンポーネントに重複キーがない場合、作成者は、問題が最初のコンポーネントでの並べ替えに還元されるとはどういう意味ですか？

配列の最初の要素がすべて異なる場合は、最初の要素を並べ替えるだけです。

于 2012-11-27T13:58:50.823 に答える
1

1-たとえば3つのアイテムがある場合：

A: {1 2 3 4 5}
B: {2 5 5 5 5}
C: {2 6 6 6 6}

Aの最初のコンポーネントは1になり、BとCは2になります

2- AとBを並べ替える必要がある場合、Aの最初のコンポーネント<Bの最初のコンポーネントなので、これ以上先に進む必要はなく、2番目の要素を比較する必要もありません。 BとCを比較するために行う

于 2012-11-27T14:02:14.947 に答える