ヒープソート

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

大きさの順番になっているヒープを構築して、その最大または最小を取り出していくことを繰り返すソート
ーポイントー
  • 最悪計算時間がnlog(n)になる非安定ソート
  • 選択ソートを改良したソート

解  説

ヒープソートは最悪計算時間がO(nlog(n))O(nlog⁡(n))になる非安定ソートです。 手順はヒープを作ることと、そのヒープから最大値または最小値を取り出すことでできます。
ヒープソート概要
1.初めに木構造の左のようなグラフを作ります。ルールは 分岐の数がすぐ下の分岐より大きいことのみです。9は5と2よりも大きく、5は1と3よりも大きいです。
上の木構造を作ってしまえばあとは繰り返しの作業です。 2. 9が最大なのは明らかなので、9を取り出します。 3. 9を取り出したら末尾の小さい数を一つ 1, 2, 3より9があったところに持ってきて、再度上が大きく下が小さくなるようなグラフを作ります。 4. そうすると再度最も大きい値が頂点に来ます。(今回なら5) あとは2.以降の繰り返しになります。
2.次以降の操作
この章を学んで新たに学べる
Comments

Reasons
>>隠す