PHP の 2 番目の部分に関する簡単な説明 -- 古典的なアルゴリズム (バブル ソートとクイック ソート) の応用_PHP チュートリアル

まず最初に、バブルソーティングの考え方について話しましょう。その後、多くの学生はバブルソーティング法とは何ですか?と尋ねます。

以下で説明しましょう:

いわゆるバブルソート方法は、小数点を前に、大きい数を後ろに置いて、2 つの隣接する数値を順番に比較することです。つまり、最初のパスでは、まず 1 番目と 2 番目の数値を比較し、小数点を前に、大きな数値を後ろに置きます。次に、2 番目の数値と 3 番目の数値を比較し、小数を前に、大きな数値を後ろに置きます。最後の 2 つの数値を比較するまで同様に、小数を前に、大きな数値を後ろに置きます。これで最初の旅行が終了し、最大数が最後に残ります。 2 番目のパスでは、引き続き最初の数値ペアから比較を開始します (2 番目の数値と 3 番目の数値の交換により、最初の数値が 2 番目の数値より小さくなくなっている可能性があるため)、小数点を最初に置きます。 、および大きな数値を配置した後、最後から 2 番目の数値まで比較が続行されます (最後から 1 番目の位置がすでに最大になっています)。2 番目のパスの終了時に、最後から 2 番目の位置で新しい最大数値が取得されます。位置 (実際には、シーケンス全体の中で 2 番目に大きい番号です)。このようにして、最終的に並べ替えが完了するまで上記のプロセスを繰り返します。

例を見てみましょう:
配列 array(23,34,12,56,43,98,89) があります。その要素をバブルソートを使用して並べ替えてみましょう。 $arr = 配列(23,34,12,56,43,98,89);
for($i=0;$i for($j=0;$j if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>

上記の例では、内部の for ループは配列内のすべての要素を 1 つずつ比較します。つまり、配列内の最初の要素と 2 番目の要素が比較され、2 番目の要素が 2 番目の要素と比較されます。 3つの要素、

以下同様に、配列の最後から 2 番目の要素が最後の要素と比較されるまで、前の要素が後の要素よりも大きい場合は、前の要素の位置を後の要素と交換します。

次に、配列内の 2 つの要素の位置を交換する方法を考えます
この問題を解決するには、中間コンテナ変数を使用できます
つまり、交換する必要がある最初の変数の値をコンテナ変数に代入し、次に交換する必要がある 2 番目の変数の値を最初の変数に代入し、次にコンテナ変数の値を 2 番目の変数に代入します。変数。

皆様にさらに深く理解していただくために、以下のシミュレーション図をご覧ください:

ステップ 1: 中間コンテナ変数 $tmp:

を宣言する

ステップ 2: $arr[$j] の値を $tmp に代入します

ステップ 3: $arr[$j+1] を $arr[$j] に代入します

ステップ 4: 中間変数の値を $arr[$j+1] に代入して交換を完了します

最後から 2 番目の要素と配列の最後の要素の比較が完了するまで、合計の比較は count($arr)-1 回行われます。 この時点で、配列の最初のソートが完了しています。つまり、配列内の最大の数値が配列の最後に配置されています。つまり、www.2cto が実行されています。コム

次に、2 番目と 3 番目のパスを実行する必要があります...ソートを一度に 1 パスずつ実行し、ソートが完了している限り、合計は count ( $arr) 回。 ここまで述べましたが、外側の for ループの意味は理解できましたか? さて、問題を考えてみましょう。配列内の要素がペアで比較される場合、各比較で最大数が排出されます。

ということは、次回の比較では前回キューに入れられた最大数との比較を行うべきではないでしょうか
？ つまり、最初のソートの後、98 が配列の最後に配置されます。これにより、次のソートで 98 を比較する必要がなく、効率が向上し、リソースが節約されます。 したがって、次のように書くことができます:
$arr = 配列(23,34,12,56,43,98,89);
for($i=0;$i for($j=0;$j if($j==count($arr)-1){
続けます;
}
if($arr[$j]>$arr[$j+1]){
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
}
}
}
?>

上記のコードでは、内側のループの実行回数は count($arr)-$i,
となります。 つまり、各パスで配列内のすべての要素を比較した後、次回ソートが実行されるときに、ソートの数が 1 つ減ります。
つまり、前回の比較で得られた最大値の比較を除外することで、効率が大幅に向上します
。 PHP の組み込み関数 microtime() を使用して、ソート前に 1 回、ソート後に 1 回実行し、その 2 回を減算して処理時間を取得できます。 比較すると、バブルソーティングの第 2 の選別方法の効率が第 1 の選別方法よりも高いと結論付けることができますが、それはここで検証できるため、ここでは詳しく説明しません。

次に、クイック ソートを使用して上記の配列を並べ替えます。

$arr = 配列(23,34,12,56,43,98,89);
関数クイック($arr){
$left = array();
$right = array();

if(count($arr) $arr を返します;
}
for($i=1;$i if($arr[0]>$arr[$i]){
$left[] = $arr[$i];
}その他{
$right[] = $arr[$i];
}
}
$left = クイック($left);
$right = クイック($right);
return array_merge($left,array($arr[0]),$right);
}
?>

いわゆるクイック ソートでは、$arr 配列内の任意の値を中間値として選択し、この値を配列内の他のすべての要素と比較します。この値より小さいものは左側に配置され、この値より大きいものは左側に配置されます。同様に、この値の左側の数値は上記のようにソートされ、右側の数値はすべての値が揃うまでソートされます。を比較します。

上記のコードを見てみましょう:
まず、クイックソートの概念を使用するには、再帰を使用する必要があります。再帰に関しては、関数を使用して自分自身を呼び出し、層ごとに深く進み、最終的に取得した値を返すというアイデアです。 .
まず、関数quick()をカスタマイズし、この関数自体を呼び出す必要があります。
ここでは、中間値として $arr[0] を使用します。これは任意に選択されるものであり、必須ではありません。 誰もが明確に考えられるように、最初に 2 つのカップに相当する 2 つの空の配列を定義します
$arr[0] を配列内のすべての値と比較します。$arr[0] より小さい値は最初のカップに配置され、$arr[0] より大きい値は 2 番目のカップに配置されます。 2 杯目は、それぞれ $left と $right です
指定された配列要素の要素が 1 つしかない場合、または空の場合は、クイック関数によって配列が返され、次の内容は実行されないと判断します。
次に、配列を走査し、走査された値を $arr[0] と比較します。 $arr[0] より小さい値は $left 配列に格納され、$arr[0] より大きい値は$left 配列に格納されると、この時点でソートが完了します。 次に、$left 配列と $right 配列に対して同じ操作を実行します。つまり、関数自体を呼び出し、$left 配列または $right 配列の配列要素が 1 つになるまで $left 配列と $right 配列を渡します。自分に電話して直接戻ってください
最後に、左の配列、$arr[0]、$right の配列をマージして、最終的な並べ替え結果を取得します。

訂正:

効率性をテストする際にエラーが発生し、効率性テストが不正確になる問題を修正しました。クラスメートから指摘を受けて何度もテストを行った結果、この配列をソートする際のクイック ソートの操作効率が以下であることがわかりました。バブルソートの効率と同じです。この 2 つはほぼ同じですが、最初のバブルソートの方が 2 番目のアルゴリズムよりもはるかに高いため、このテスト結果は各アルゴリズムの効率を正確に計算するための参考としてのみ使用できます。 、アルゴリズム内でソート回数をカウントする必要があります。

この問題にご注目いただき、修正していただきありがとうございます。これはオープンなプラットフォームです。自由に話し、もっとコミュニケーションをとり、一緒に進歩してください。


zdrjlampより抜粋

http://www.bkjia.com/PHPjc/478287.html

www.bkjia.com本当http://www.bkjia.com/PHPjc/478287.html技術記事まず、バブル ソートの考え方について説明します。次に、多くの学生が、バブル ソート法とは何ですか? と尋ねます。以下で説明します。いわゆるバブル ソート法は、2 つの隣接する数値を順番に比較し、小数点を並べ替えることです。 .