ヒープソートでソートする方法

1. 初期ヒープの構築:

ヒープを初期化するとき、すべての非リーフ ノードがフィルターされます。 。

最後の非終端要素の添字は [n/2] 切り捨てられるため、フィルタリングは [n/2] 番目の切り捨て要素から開始して後ろから前に調整するだけで済みます。

たとえば、配列が与えられた場合、まず配列要素に基づいて完全なバイナリ ツリーを構築します。

その後、リーフではない最後のノードから、親ノード、左の子、右の子とその都度比較・交換が行われ、交換により子ノードがヒープの性質を満たさなくなる可能性があります。したがって、この交換の後は毎回、交換された子ノードを再調整する必要があります。

2. ヒープのソートを実行します:

初期ヒープを取得したら、それをソートできます。

ヒープ ソートは選択ソートです。作成される最初のヒープは、最初の順序付けされていない領域です。

ソートが開始されると、ヒープの先頭要素が最初に出力され(それが最も高い値であるため)、ヒープの先頭要素と最後の要素が入れ替わります。このようにして、n 番目の位置 ( (つまり、最後の位置) が順序付けされた領域として使用され、前の n-1 個の位置はまだ順序付けされていない領域です。順序付けされていない領域を調整します。ヒープを取得した後、ヒープの先頭と最後の要素を交換して、長さがご注文エリアの面積は2となります。 。 。

この操作を続けて、残りの要素をヒープに再調整し、ヒープの先頭要素を順序付き領域に出力します。各スワップの結果、順序付けされていない領域は -1 になり、順序付けされた領域は 1 になります。このプロセスは、順序付けされた領域の長さが n-1 になるまで繰り返され、ソートが完了します。

3. ヒープのソート例:

まず、次のように初期ヒープ構造を確立します:

次に、では、ヒープの先頭の要素と最後の要素を入れ替えますが、このとき最後の位置を順序付け領域として使用し（順序付け済み領域は黄色で表示されます）、その後、他の非順序付け領域のヒープを調整します。大きな上部ヒープでは、ヒープの先頭と最後の要素を交換します。最後から 2 番目の要素の位置...

このプロセスを繰り返します:

最後に、順序付けされた領域の拡張が完了します。つまり、ソートが完了します。

##ソートのプロセスから、次のことがわかります。昇順を取得したい場合は大きな上部ヒープを作成し、降順を取得したい場合は小さな上部ヒープを作成します。

以上がヒープソートでソートする方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。