PHP ソートアルゴリズムヒープソート (Heap Sort)-PHPチュートリアル-php.cn

この記事では、PHP ソートアルゴリズムヒープソート (Heap Sort) を主に紹介し、ヒープソートの原理、実装方法、および関連する使用上の注意事項をサンプルの形で詳しく分析します。この記事では、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);

ログイン後にコピー

実行結果:

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) 時間計算量よりも明らかにパフォーマンスがはるかに優れています。

ヒープソートは不安定なソート方法です。

この記事は「Dahua データ構造」から参照されています。将来の参考のためにここに記録されているだけです。批判しないでください。

PHP ソート アルゴリズム ヒープ ソート (Heap Sort)

PHP ソートアルゴリズムヒープソート (Heap Sort)