PHP は 4 つの並べ替えアルゴリズムを実装します_PHP チュートリアル-PHPチュートリアル-php.cn

PHP は 4 つの並べ替えアルゴリズムを実装します_PHP チュートリアル

WBOY

リリース： 2016-07-13 10:05:49

オリジナル

856 人が閲覧しました

phpは4つのソートアルゴリズムを実装しています

この記事は「PHP100中国語ウェブサイト」からのものです

前提: バブルソート、クイックソート、選択ソート、および挿入ソートを使用して、次の配列内の値を小さい値から大きい値の順に並べ替えます。
$arr(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);
//このレイヤーループは、バブルする必要があるラウンドの数を制御します
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;
}
}
}
$arr を返します;
}

2. 並べ替えを選択します

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

コードの実装:
関数 selectSort($arr) {
//二重ループが完了し、外側の層はラウンド数を制御し、内側の層は比較の数を制御します
$len=count($arr);
for($i=0; $i //まず最小値の位置を仮定します $p = $i;

for($j=$i+1; $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;
}
}
// 最終結果を返します
$arr を返します;
}

3. 挿入ソート

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

コードの実装:
関数 insertSort($arr) {
$len=カウント($arr); for($i=1, $i $tmp = $arr[$i];
// 内部ループの制御、比較、挿入 for($j=$i-1;$j>=0;$j--) {
if($tmp //挿入された要素の方が小さいことが判明したので、位置を入れ替え、後の要素を前の要素と交換します
$arr[$j+1] = $arr[$j]; $arr[$j] = $tmp;
} その他 {
// 移動する必要のない要素が見つかった場合、それはソートされた配列であるため、前の要素を再度比較する必要はありません。
休憩;
}
}
}
$arr を返します;
}

4.クイックソート

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

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