PHP ヒープソートアルゴリズムの分析例-PHPチュートリアル-php.cn

PHP ヒープソートアルゴリズムの分析例

php中世界最好的语言

リリース： 2023-03-26 06:16:01

オリジナル

1627 人が閲覧しました

今回は 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中文网其它相关文章！