この記事は主に PHP で実装されたヒープ ソート アルゴリズムを詳しく紹介します。興味のある方は参考にしていただければ幸いです。
アルゴリズムの紹介:
ここで、「Dahua データ構造」の冒頭を直接引用します:
前述したように、ソート対象の n レコードの中から最小のレコードを選択する単純な選択ソートでは、n - 1 を比較する必要があります。これは当然のことですが、最初のデータを見つけるために何度も比較するのが普通です。そうでない場合、それが最小のレコードであることを知る方法はありません。
残念ながら、この操作では各パスの比較結果は保存されません。前のパスで多くの比較が行われているため、ソートの結果として、後のパスの比較結果が重くなります。これらの比較、これらの比較操作は次の並べ替えパスで繰り返されるため、さらに多くの比較が記録されます。
毎回最小のレコードを選択し、比較結果に基づいて他のレコードに対応する調整を行うことができれば、ソートの全体的な効率は非常に高くなります。ヒープ ソートは単純な選択ソートを改良したものであり、この改良の効果は非常に明白です。
基本的な考え方:
ヒープのソートを紹介する前に、まずヒープを紹介しましょう:
「Dahua データ構造」での定義: ヒープは次のプロパティを持つ完全なバイナリ ツリーです: 各ノードの値が大きくなります。または 左右の子ノードの値と等しい場合、大きなトップ ヒープ (大きなルート ヒープ) になります。または、各ノードの値がその左右のノードの値以下である場合。 、小さなトップヒープ(小さなルートヒープ)になります。
これを見たとき、私も「ヒープは完全なバイナリツリーなのか?」という点に疑問を感じました。ネット上では完全なバイナリツリーではないという意見もありますが、ヒープが完全なバイナリツリーであるかどうかは関係ありません。ツリー、私はまだ自分の意見を保留しています。ここでは、主に保存と計算を容易にするために、完全なバイナリ ツリーの形式で大きなルート ヒープ (小さなルート ヒープ) を使用していることだけを知っておく必要があります (利便性については後で説明します)。
ヒープソートアルゴリズム:
ヒープソートは、ヒープ(大きなルートヒープを想定)を使用してソートする方法です。その基本的な考え方は、ソートされるシーケンスを大きなルートヒープに構築することです。このとき、シーケンス全体の最大値はヒープの先頭のルートノードとなる。それを削除し (実際には、それをヒープ配列の最後の要素と交換します。このとき、最後の要素が最大値になります)、残りの n - 1 シーケンスをヒープに再構築して、n 要素を取得します。次に小さい値。これを繰り返し実行すると、順序付けられたシーケンスが得られます。
ラージルートヒープソートアルゴリズムの基本操作:
①ヒープの構築は、len/2から開始して最初のノードに向かってヒープを継続的に調整するプロセスです。ここで、lenは要素の数です。ヒープ。ヒープを構築するプロセスは線形プロセスであり、ヒープを調整するプロセスは常に len/2 から 0 まで呼び出されます。これは、o(h1) + o(h2) ... + o(hlen/2) と同等です。ここで、h はノードの深さを表し、len /2 はノードの数を表します。これは合計プロセスであり、結果は線形 O(n) です。
②調整ヒープ: 調整ヒープはヒープの構築プロセスで使用され、ヒープのソートプロセスでも使用されます。アイデアは、ノード i とその子ノード left(i) および right(i) を比較し、最大 (最小) 値がノード i ではなくその子ノードの 1 つである場合に、3 つのうちの最大 (または最小) を選択することです。そこで、ノード i はノードと対話し、ヒープ調整プロセスを呼び出します。これは再帰的なプロセスです。ヒープを調整するプロセスの時間計算量は、ヒープの深さに関係します。これは、深さ方向に沿って調整されるため、lgn の操作です。
③ヒープソート:上記2つの処理によりヒープソートが行われます。 1 つ目は、要素に基づいてヒープを構築することです。次に、ヒープのルート ノードを取り出し (通常は最後のノードと交換します)、最初の len-1 ノードでヒープ調整プロセスを続行し、すべてのノードが取り出されるまでルート ノードを取り出します。ヒープソートプロセスの時間計算量は O(nlgn) です。ヒープの構築の時間計算量は O(n) (1 回の呼び出し)、ヒープの調整の時間計算量は lgn であり、n-1 回呼び出されるため、ヒープのソートの時間計算量は O(nlgn) です。
このプロセスを明確に理解するには多くの図が必要ですが、私は怠け者です。 。 。 。 。 。
アルゴリズム実装:
<?php //堆排序(对简单选择排序的改进) function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } //调整 $arr[$start]的关键字,使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆(根节点最大的完全二叉树) //注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 (数组开始下标为 0 时) function HeapAdjust(array &$arr,$start,$end){ $temp = $arr[$start]; //沿关键字较大的孩子节点向下筛选 //左右孩子计算(我这里数组开始下标识 0) //左孩子2 * $start + 1,右孩子2 * $start + 2 for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){ if($j != $end && $arr[$j] < $arr[$j + 1]){ $j ++; //转化为右孩子 } if($temp >= $arr[$j]){ break; //已经满足大根堆 } //将根节点设置为子节点的较大值 $arr[$start] = $arr[$j]; //继续往下 $start = $j; } $arr[$start] = $temp; } function HeapSort(array &$arr){ $count = count($arr); //先将数组构造成大根堆(由于是完全二叉树,所以这里用floor($count/2)-1,下标小于或等于这数的节点都是有孩子的节点) for($i = floor($count / 2) - 1;$i >= 0;$i --){ HeapAdjust($arr,$i,$count); } for($i = $count - 1;$i >= 0;$i --){ //将堆顶元素与最后一个元素交换,获取到最大元素(交换后的最后一个元素),将最大元素放到数组末尾 swap($arr,0,$i); //经过交换,将最后一个元素(最大元素)脱离大根堆,并将未经排序的新树($arr[0...$i-1])重新调整为大根堆 HeapAdjust($arr,0,$i - 1); } } $arr = array(9,1,5,8,3,7,4,6,2); HeapSort($arr); var_dump($arr);
時間計算量分析:
その実行時間は、最初の建設ペアと再構成杭の繰り返しのスクリーニングでのみ消費されます。
一般に、ヒープソートの時間計算量は O(nlogn) です。ヒープ ソートは元のレコードのソート状態に影響されないため、最高、最低、平均の時間計算量は O(nlogn) です。これは、バブリング、単純な選択、直接挿入の O(n^2) 時間計算量よりも明らかにパフォーマンスがはるかに優れています。
関連おすすめ:
PHPソートアルゴリズムシリーズ_phpスキルでのバケットソートの詳細説明
以上がPHPソートアルゴリズムヒープソートの詳細説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。