PHP ヒープ ソートの実装原理と応用方法、PHP ヒープ ソートの実装原理_PHP チュートリアル

PHPヒープソート実装原理と応用方法、PHPヒープソート実装原理

この記事の例では、PHP ヒープ ソートの実装原理と適用方法について説明します。参考のためにみんなで共有してください。具体的な分析は次のとおりです:

ここでは、プログラムの可読性を確保するために、PHP を記述言語として使用しています。PHP プログラムのヒープに関するいくつかの概念は次のとおりです。

n が現在の配列のキーであると仮定すると、n の親ノードは n>>1 または n/2 (割り算可能) であり、n の左の子ノードは l= n $arr=配列(1,8,7,2,3,4,6,5,9);

配列 $arr の元の構造は次のとおりです:

1

                                                                             7
                                                                                2 3 4 6
/
5 9
ヒープソート($arr);print_r($arr);

ソート後に生成される標準的なスモールトップヒープ構造は次のとおりです:

1

                                                                         3

                                                                                    4 5 6 7

/
8 9
つまり、配列: array(1,2,3,4,5,6,7,8,9):



コードをコピーします

コードは次のとおりです:

関数ヒープソート(&$arr)
{
//最後の要素ビットを検索します
$last=count($arr); //$arr[0] は通常、ヒープのソートでは無視されます
array_unshift($arr,0); //最後の非リーフノード
$i=$last>>1;
//大きな上部ヒープに編成し、最大数値をヒープの先頭に移動し、最大数値をヒープの末尾と交換し、後続の計算では配列の後端 (最後) の最大数値を無視します。ヒープの先頭 (last=ヒープの先頭)
ながら (本当)
                                                                   Adjustnode($i,$last,$arr); If($i>1)
                                                                       // ノード ポインタを移動し、リーフ以外のノードをすべて走査します
$i--;                                                                                       その他
                                                                       //クリティカルポイント last=1、つまりすべてのソートが完了しました
If($last==1)ブレイク
// i が 1 の場合、仕上げの各パイルが最大数 (パイル トップ、$ arr [1]) を取得し、ルート ノードでヒープを繰り返すことを意味します スワップ($arr[$last],$arr[1]); // 配列数のシーケンスの最大数を維持し、配列がソートされるときに配列の後ろにあるソートされた要素が一致しないように、臨界点を最後に定義します。 $last--;                                                                                       }
//最初の配列要素をポップします
配列_shift($arr); }

// 現在のツリー ノード ($n) を整理します。重要な点 $last 以降は並べ替えられた要素です
関数adjustnode($n,$last,&$arr)
{
                                                                                                                                    If(!isset($arr[$l])||$l>$last) を返す ;                                                                                                                                                                  
//右の子が左の子より大きい場合は、親ノードの右の子を
より大きくする if($r<=$last&&$arr[$r]>$arr[$l]) $l=$r; //子ノード $l が親ノード $n より大きい場合、親ノード $n と交換します
If($arr[$l]>$arr[$n])                                                                    //子ノードの値 ($l) を親ノードの値 ($n) に交換します
swap($arr[$l],$arr[$n]); //交換後も、親ノード ($n) の値 ($arr[$n]) はアトミック ノード ($l) の子ノードの値よりも小さい可能性があるため、アトミックノード ($l) は再帰を使用して実装されるように調整する必要があります
Adjustnode($l,$last,$arr); }
}

//2つの値を交換します
関数スワップ(&$a,&$b)
{
$a=$a ^ $b;
$b=$a ^ $b;
$a=$a ^ $b; }

この記事で説明した内容が皆様の PHP プログラミング設計に役立つことを願っています。

http://www.bkjia.com/PHPjc/936800.html

www.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/936800.html技術記事 PHP ヒープ ソートの実装原理と応用方法、PHP ヒープ ソートの実装原理と応用方法について例を示して説明します。参考のためにみんなで共有してください。具体的な分析は次のとおりです:...