1

{0,2,10,23,65} や {3,5,8..} など、既に並べ替えられていることがわかっているセットがあるとします。任意の数のソート済みセットを 1 つのソート済みセットに結合できる最適なソート アルゴリズムは何でしょうか? このタイプのソートはどれほど効率的でしょうか?

4

3 に答える 3

4

それらを並べ替える必要はありません。マージする必要があります。これはO(M+N)、2 つの部分の現在の要素を参照する 2 つのインデックスを保持し、2 つのうち小さい方を最終シーケンスに追加し、インデックスを 1 つ進める単純なループを使用して行われます。

擬似コードは次のとおりです。

int[] parts1, parts2 // Sorted parts
int i = 0, j = 0;
while i != parts1.Length || j != parts2.Length
    if i != parts1.Length || j != parts2.Length
        if parts1[i] < parts2[j]
            res.Add(parts1[i++])
        else
            res.Add(parts2[j++])
    else if i != parts1.Length
        res.Add(parts1[i++])
    else
        res.Add(parts2[j++])

各ステップで、ループはiまたはjの実行parts1.Lenght + part2.Length回数だけ進みます。

于 2012-05-09T23:41:59.213 に答える
2

最も簡単な方法は、リストの先頭を比較し、最小のものを取得して、並べ替えられたセットに追加することです。すべてのリストが空になるまで繰り返します。

効率的に言えば、時間に対して常に直線的です。合計でマージする必要があるアイテムの数だけ時間がかかります。

これは実際にはMergesortの第 2 段階です。

于 2012-05-09T23:43:16.217 に答える
1

セットにO(n)要素があるとします。O(k)標準のマージは になりますO(n * k)。

2セットしか持っていない場合、これは大したことではありません。1000あれば可能です。その場合、次に小さい要素で編成されたセットの優先キューを保持できます。このバリアントはO(n log(k)).

于 2012-05-10T07:26:15.093 に答える