3

ヒープソートは「分割統治」ソートまたは優先キューソートと見なされますか？

また、バブルソートがどのカテゴリに当てはまるか（恐ろしいことを除く）。

ヒープソートは一般に「分割統治」ソートと見なされますが、優先キューソートの場合もあります。厳密にはどちらか一方ですか？それとも、それはどのように両方ですか？バブルソートが何と考えられるかについては何も見つかりません。

4

3 に答える 3

5

HeapSortアルゴリズムが問題をサブ問題に細分化することは決してないので、「分割統治」とは見なされないと思います。HeapSortを実行するには、アルゴリズムが実行されるExtractMinかExtractMax、ヒープが空になるまで実行されます。これらのアクションはO(logn)、それぞれの後に、ExtractMinまたはExtractMaxその半順序を維持するためにHeap行う必要があるためです。Heapify最後に、O(nlogn)それがするので、n ExtractMinまたはのコストがかかりExtractMaxます。

これが擬似コードです

HeapSort()
 heap
 new_ ordered_collection
 while(heap.NotEmpty)
   new_ ordered_collection.add(heap.ExtractMin)//or ExtractMax
   heap.Heapify //could be MaxHeapify or MinHeapify
 return new_ ordered_collection

ヒープの最小要素または最大要素をポップアウトするExtractMinことに注意してください。ExtractMax

ご覧のとおり、「分割統治」戦略は見当たりません。

ただし、heap.Heapifyヒープの半順序に基づいて要素を並べ替えます。これは、各ノードとその2つの子の間の関係を定義します。これによりheap.Heapify、「分割統治」戦略が適用されますが、これはDataStructre自体のアルゴリズムではありません。

そして、バブルソートはnaiveアルゴリズムです。

于 2013-03-19T01:29:25.703 に答える
0

ヒープソートには、「分割統治」アルゴリズム（クイックソートなど）の時間計算量がありますが、分割統治アルゴリズムのようには動作しません。

データを「ソート済み」セクションと「未ソート」セクションに分割するため、実際には一種の選択ソートです。ヒープデータ構造を利用して、各ステップでソートされていないリストから最小要素をより効率的に選択します。このため、「優先キューソート」と言えますが、個別のヒープを構築するのではなく、操作全体をインプレースで実行できることに注意してください。

ヒープソートは通常、クイックソートよりも優れていますが、クイックソートの複雑さは最悪の場合ですO(N^2)（ヒープソートの最悪の場合とは異なりますO(N.logN)）。

バブルソートもインプレースアルゴリズムですが、「ナイーブ」と見なされます。

于 2013-03-19T01:34:03.830 に答える
0

上で述べたように、ヒープソートは間違いなく「分割統治」アルゴリズムではありません。ヒープソートは、ヒープデータ構造を使用してその要素を効率的にソートします。ヒープソートは、優先キューを使用した選択ソートと考えることができます。

分割統治アルゴリズムには、次の特徴があります。

1）タスクを同じタスクのより小さなインスタンスであるサブタスクに分割します2）サブタスクを再帰的に解決します3）結果を適切に組み合わせます

ご覧のとおり、ヒープソートはこのタイプのアルゴリズムとしては適格ではありません。唯一の類似点は、分割統治アルゴリズムの構造がバイナリツリーの構造を反映していることです（これは通常、ヒープソートが優先キューを実装するために使用するものです）。

于 2013-07-09T20:18:34.500 に答える