ホームページ > 記事 > バックエンド開発 > PHPソートアルゴリズムヒープソートの詳細説明

PHPソートアルゴリズムヒープソートの詳細説明

小云云オリジナル: 2018-01-08 10:08:271646ブラウズ

この記事は主に 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ソートアルゴリズムヒープソートの詳細説明

関連記事