0

どのような場合にヒープソートを使用できますか? ご存知のように、ヒープソートにはn× lg(n)の複雑さがあります。ただし、クイックソートやマージソートよりも使用頻度ははるかに低くなります。では、このヒープソートを正確に使用するのはいつで、その欠点は何ですか?

4

3 に答える 3

1

ヒープソートの特徴

  • O(nlogn) 時間 ベスト、平均、ワースト ケースのパフォーマンス
  • O(1) 余分なメモリ

どこで使用しますか？

  • 保証された O(nlogn) パフォーマンス。Quicksort の O(n^2) は非常に遅くなる可能性があるため、必ずしも非常に高速なパフォーマンスを必要としないが、保証された O(nlogn) パフォーマンス (ゲームなど) が必要な場合。それでは、Mergesort を使用しないのはなぜですか? O(n) 余分なメモリが必要だからです。
  • クイックソートの最悪のケースを回避するため。C++ のstd::sortルーチンは通常、Introsort と呼ばれる Quicksort のバリエーションを使用します。これは、Quicksort の再帰が深くなりすぎて、最悪のケースが発生したことを示す場合に、Heapsort を使用して現在のパーティションをソートします。
  • 突然停止しても部分的にソートされた配列。ヒープソートが何らかの形で突然停止した場合、部分的にソートされた配列が得られます。役に立つかもしれません。

短所

  • クイックソートと比較して比較的遅い
  • キャッシュが非効率的
  • 安定していない
  • あまり適応的ではありません (ある程度ソートされた配列が与えられた場合、速くなりません)
于 2013-09-10T18:05:59.433 に答える
0

アルゴリズムの並べ替えに関するウィキペディアの記事に基づいて、ヒープソートとマージソートはすべてO(n log n)、最良、平均、最悪のケースで同じ時間の複雑さを持っているようです。

クイックソートには、 (a)の最悪の場合の時間の複雑さがあるという欠点があります。O(n2)

マージソートには、そのメモリの複雑さがヒープソートの複雑さであるという欠点がありO(n)ますO(1)。一方、マージソートは安定ソートですが、ヒープソートはそうではありません。

したがって、メモリ使用量を最小限に抑えるために、並べ替えの安定性を気にしない場合は、マージソートよりもヒープソートを選択します。安定性が必要な場合は、MergeSort を選択します。

または、より正確には、ソートするデータが大量にあり、それを行うために独自のアルゴリズムをコーディングする必要がある場合は、それを行います。ほとんどの場合、データ セットが大量になるまで、この 2 つの違いは問題になりません。

実際、他のソートが提供されていない実際の本番環境でバブルソートを使用したこともあります。理由は次のとおりです。

  • 書くのは信じられないほど簡単です (最適化されたバージョンでも)。
  • データに特定のプロパティ (いくつかの項目を追加する前に既にほとんどが並べ替えられている小さなデータセットまたはデータセット) がある場合、十分に効率的です。

同様gotoに、複数のリターンポイント、一見悪いアルゴリズムにもその場所があります:-)

(a)そして、なぜ C が非効率的なアルゴリズムを使用するのか疑問に思う前に、それは (必然的に) 使用しません。名前にもかかわらず、qsort裏で Quicksort を使用する義務はありません。これはよくある誤解です。他のアルゴリズムのいずれかを使用することもできます。

于 2013-08-13T09:16:01.120 に答える