4つの基本的なソートアルゴリズムのPHPコード実装

アルゴリズムはプログラムの核であり、アルゴリズムの品質がプログラムの品質を決定すると多くの人が言います。初心者の PHP 開発者として、私はアルゴリズムに触れることはほとんどありません。ただし、プログラム開発に不可欠なツールである基本的なソートアルゴリズムを習得する必要があります。ここでは、バブルソート、挿入ソート、選択ソート、クイックソートの 4 つの基本的なアルゴリズムを紹介し、アルゴリズムの背後にある考え方を分析します。

[[129906]]

前提条件: バブルソート、クイックソート、選択ソート、挿入ソートを使用して、次の配列の値を小さい順に並べ替えます。

1,43,54,62,21,66,32,78,36,76,39 をコピーします。

1. バブルソート

思考分析：分類する数字のグループにおいて、現在分類されていない数列について、前方から後方へ順番に隣接する 2 つの数字を比較して調整し、大きい数字が下がり、小さい数字が上がるようにします。つまり、隣接する 2 つの数値を比較し、その順序が順序要件と逆であることがわかった場合は、それらの数値が交換されます。

 $arr = 配列 ( 1 、 43 、 54 、 62 、 21 、 66 、 32 、 78 、 36 、 76 、 39 );
関数 bubbleSort($arr)
 {
  $len = count($arr);
 //このレイヤーループは必要なバブリングの回数を制御します 
 ($i= 1 ;$i<$len;$i++)の場合
  { // このループ層は、各ラウンドで数字が出現する回数を制御し、比較する必要がある回数を制御するために使用されます。  
 ($k= 0 ;$k<$len-$i;$k++)の場合
    {
 ($arr[$k]>$arr[$k+ 1 ])の場合
        {
            $tmp=$arr[$k+ 1 ];
            $arr[$k+ 1 ] = $arr[$k];
            $arr[$k] = $tmp;
        }
    }
  }
 $arrを返します。
 }

2. 選択ソート

思考分析: 並べ替える数字のグループの中で、最も小さい数字を選択し、最初の位置の数字と交換します。次に、残りの数字の中から最小の数字を見つけて、それを 2 番目の位置の数字と交換し、最後から 2 番目の数字が最初の数字と比較されるまでこのサイクルを繰り返します。

関数selectSort($arr) {
 //二重ループが完了しました。外側の層はラウンド数を制御し、内側の層は比較回数を制御します。  
 $len = count($arr);
 ($i= 0 ; $i<$len- 1 ; $i++)の場合{
 //まず最小値の位置を想定する 
 $p = $i; 
 
 ($j=$i+ 1 ; $j<$len; $j++)の場合{
 //$arr[$p]は現在知られている最小値です 
 ($arr[$p] > $arr[$j])の場合{
 // 比較して小さい方を見つけ、最小値の位置を記録します。そして、次回の比較には既知の最小値を使用します。  
 $p = $j;
 }
 }
 //現在の最小値が決定され、$p に保存されました。最小値の位置が現在想定されている位置 $i と異なることが判明した場合、位置を交換することができます。  
 ($p != $i)の場合{
 $tmp = $arr[$p];
 $arr[$p] = $arr[$i];
 $arr[$i] = $tmp;
 }
 }
 //最終結果を返す 
 $arrを返します。
 }

#p#

3. 挿入ソート

思考分析: 並べ替える数字のグループでは、前の数字がすでに順序どおりになっていると仮定して、n 番目の数字を前の順序どおりになっている数字に挿入して、これらの n 個の数字も順序どおりになるようにする必要があります。すべてが正常になるまでこのサイクルが繰り返されます。

関数 insertSort($arr) {
 $len = count($arr);
 ($i= 1 、$i<$len; $i++)の場合{
 $tmp = $arr[$i];
 //内部ループ制御、比較、挿入 
 ($j=$i- 1 ;$j>= 0 ;$j--)の場合{
 ($tmp < $arr[$j])の場合{
 //挿入された要素が小さいことがわかったので、位置を入れ替え、後者の要素を前の要素と入れ替えました 
 $arr[$j+ 1 ] = $arr[$j];
 $arr[$j] = $tmp;
 }それ以外{
 // 移動する必要のない要素に遭遇した場合、それはソートされた配列であるため、以前の要素を再度比較する必要はありません。  
壊す;
 }
 }
 }
 $arrを返します。
 }

4. クイックソート

思考分析: ベースライン要素 (通常は最初の要素または最後の要素) を選択します。 1 回のスキャンで、ソートするシーケンスが 2 つの部分に分割され、1 つの部分はベンチマーク要素よりも小さく、もう 1 つの部分はベンチマーク要素以上になります。このとき、ベンチマーク要素はソート後に正しい位置に配置され、その後同じ方法を再帰的に使用して 2 つの分割部分をソートします。

関数クイックソート($arr) {
 //まず続行するかどうかを決定する 
 $arr の長さを数えます。
 ($length <= 1 )の場合{
 $arrを返します。
 }
 //最初の要素をベンチマークとして選択する 
 $base_num = $arr[ 0 ];
 //ルーラー以外のすべての要素を走査し、サイズに応じて2つの配列に格納します 
 // 2つの配列を初期化する 
 $left_array = array(); // ベンチマークより小さい 
 $right_array = array(); //ベンチマークより大きい 
 ($i= 1 ; $i<$length; $i++)の場合{
 ($base_num > $arr[$i])の場合{
 //左の配列に挿入 
 $left_array[] = $arr[$i];
 }それ以外{
 //右側に置く 
 $right_array[] = $arr[$i];
 }
 }
 // 次に、左と右の配列を同じようにソートしてこの関数を再帰的に呼び出します 
クイックソート
クイックソート
//マージ 
 array_merge($left_array、array($base_num)、$right_array)を返します。
 }