ホームページ >バックエンド開発 >PHPチュートリアル >PHP ヒープソートアルゴリズムの分析例
今回は PHP ヒープソートアルゴリズムの分析例をお届けします。 PHP ヒープソートアルゴリズムの分析例についての 注意事項 は次のとおりです。
これは単純な 選択ソート です。最初のデータを見つけるには、通常、 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);
実行結果:
array(9) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) [5]=> int(6) [6]=> int(7) [7]=> int(8) [8]=> int(9) }
时间复杂度分析:
它的运行时间只要是消耗在初始构建对和在重建堆屎的反复筛选上。
总体上来说,堆排序的时间复杂度是 O(nlogn)。由于堆排序对原始记录的排序状态并不敏感,因此它无论是最好、最差和平均时间复杂度都是 O(nlogn)。这在性能上显然要远远好于冒泡、简单选择、直接插入的 O(n^2) 的时间复杂度了。
堆排序是一种不稳定排序方法。
相信看了本文案例你已经掌握了方法,更多精彩请关注php中文网其它相关文章!
推荐阅读:
以上がPHP ヒープソートアルゴリズムの分析例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。