PHP での 4 つの基本的な並べ替えアルゴリズムのコード実装

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

前提: バブルソート、クイックソート、選択ソート、挿入ソートを使用して、以下の配列内の値を小さいものから大きいものの順に並べ替えます。
$arr(1,43,54,62,21,66,32,78,36,76,39); 1. バブルソート

アイデア分析: 並べ替える数字のグループで、まだ並べ替えられていない数列について、大きい数字が下に沈むように、隣り合う 2 つの数字を前から後ろに比較して調整します。小さい方が上に上がっていきます。つまり、2 つの隣接する数値が比較され、その順序が順序要件と逆であることが判明した場合は常に、それらの数値が交換されます。

{
 $len=count($arr) );
 //このループ層はバブルする必要があるラウンド数を制御します
 for($i=1;$i { //このループ層はバブル数を制御するために使用されます各ラウンド時間で比較する必要があるバブルの数
 for($k=0;$k {
 if($arr[$k]>$arr[$k+ 1])
 {
 $tmp= $arr[$k+1];
 $arr[$k+1]=$arr[$k];
 $arr[$k]=$tmp;
 }
 }
 }
 return $arr;
}

アイデア分析:

並べ替える一連の数値の中から最小の数値を選択し、それを最初の位置の数値と交換します。次に、残りの数値の中から最小のものを見つけて、それを 2 番目の数値と交換します。このサイクルは、最後から 2 番目の数値が最後の数値と比較されるまで続きます。

for ($i=0; $i//最初に最小値の位置を仮定します
$p = $i;

for($j=$i+1; $j< ;$len; $j++) {
 //$arr[$p] は現在知られている最小値です
if($arr[$p] > $arr[$j]) {
//比較して小さい値を見つけます、最小値の位置を記録し、次の比較で既知の最小値を使用します。
$p = $j;
}
}
//現在の最小値の位置が決定され、$p に保存されました。最小値の位置が現在仮定されている位置$iと異なることが判明した場合には、位置を入れ替えることができる。
if($p != $i) {
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
//最終結果を返す
return $arr;
}


コードをコピー

並べ替える一連の数値において、前の数値がすでに順序どおりであると仮定すると、今度は、これらの n 数値も順序どおりになるように、前の順序の数値に n 番目の数値を挿入する必要があります。すべてが整うまでこのサイクルを繰り返します。

function insertSort($arr) {

$len=count($arr);

for($i=1, $i$tmp = $arr[$i] ;

//内部ループ制御、比較と挿入

for($j=$i-1;$j>=0;$j--) {

if($tmp < $arr[$j]) {

//挿入された要素を小さくする必要があることを確認し、位置を交換し、後の要素を前の要素と交換します

$arr[$j+1] = $arr[$j];

$arr[$j] = $ tmp ;

} else {

//移動する必要のない要素が見つかった場合、それはソートされた配列であるため、前の要素を再度比較する必要はありません。

break;

}

}

}

return $arr;

}

コードをコピー

4. クイックソート

アイデア分析: ベンチマーク要素 (通常は最初の要素または最後の要素) を選択します。 1 回のスキャンで、ソート対象の列が 2 つの部分に分割され、1 つの部分は参照要素より小さく、もう 1 つの部分は参照要素以上になります。このとき、ベース要素はソート後の正しい位置にあり、分割された 2 つの部分も同様に再帰的にソートされます。

function QuickSort($arr) {
//最初に続行する必要があるかどうかを決定します
$length = count($arr);
if($length <= 1) {
return $arr;
}
 //最初の要素をベースとして選択します
$base_num = $arr[0];
//ルーラーを除くすべての要素をスキャンし、サイズ関係に従って 2 つの配列に入れます
//2 つの配列を初期化します
$left_array = array(); // 基数より小さい
 $right_array = array(); // 基数より大きい
for($i<$length; $i++) {
if($base_num > $ arr[ $i]) {
//左側の配列に入れます
$left_array[] = $arr[$i];
} else {
//右側に入れます
$right_array[] = $arr [$i];
}
}
//次に、左と右の配列に対して同じソートを実行し、この関数を再帰的に呼び出します
$left_array = Quick_sort($left_array);
$right_array = Quick_sort($right_array);
/ /Merge
return array_merge ($left_array, array($base_num), $right_array);
}

出典: php100

4種類、PHP