古典的なアルゴリズムの学習 - ヒープソート_PHP チュートリアル
- WBOYオリジナル
- 2016-07-12 08:54:03897ブラウズ
古典的なアルゴリズムの学習 - ヒープソート
ヒープソートは他のソートより少し面倒なソートで、ヒープの性質を利用した選択ソートです。ヒープは実際には完全なバイナリ ツリーです。非リーフ ノードのキーがその左右の子ノードより大きくないか、小さくない限り、ヒープを形成できます。ヒープは、大きなトップパイルと小さなトップパイルに分かれています。上記の特性から、大きなヒープの先頭にあるキーワードがすべてのキーワードの中で最大であり、小さなヒープの先頭にあるキーワードがすべてのキーワードの中で最小であることがわかります。ヒープ ソートは、クイック ソートと同様に不安定なソートです。サンプルコードはhttps://github.com/chenyufeng1991/HeapSort
にアップロードされましたヒープソートの考え方：ヒープの先頭に最大キー（最小キー）が記録されるラージトップヒープ（スモールトップヒープ）の特徴を活かし、最大キーの選択が簡単になる毎回の乱れからの記録（最低記録）。注: 大きな上部ヒープは増加シーケンスを構築し、小さな上部ヒープは降順シーケンスを構築します。
(1) 並べ替えるキーワードの最初のシーケンス (R0、R1...Rn-1) を、最初の順序付けされていない領域である大きな上部ヒープに構築します。
(2) 先頭要素 R[0] を最後の要素 R[n-1] と交換すると、新しい不規則領域 (R0, R1...Rn-2) と新しい順序領域が得られます。 . (Rn-1) を満たし、R[0,1...n-2] (3) 交換後の新しいヒープ先頭 R[0] はヒープの性質に違反する可能性があるため、現在の未順序領域 (R0, R1...Rn-2) を新しいヒープに合わせる必要があり、次に R[0] を再度変更します。] が無秩序領域の最後の要素と交換され、新しい無秩序領域 (R0、R1...Rn-3) と新しい順序領域 (Rn-2、Rn-1) が得られます。領域内の要素の数が n-1 になるまでこのプロセスを繰り返し、ソート プロセス全体が完了します。
操作プロセスは次のとおりです:
(1) ヒープを初期化します: [0...n-1] をヒープとして構築します。
(2) 現在の順序なし領域の先頭要素 R[0] を間隔の最後のレコードと交換し、新しい順序なし領域を新しいヒープに調整します。
したがって、ヒープのソートで最も重要な 2 つの操作は、初期ヒープと調整ヒープの構築です。実際、初期ヒープの構築はヒープを調整するプロセスでもありますが、初期ヒープの構築はリーフ以外のすべてのヒープを調整することです。ノード。サンプルコードは次のとおりです:
リーリー
http://www.bkjia.com/PHPjc/1121830.html声明：
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。