PHPバブルソート(Bubble Sort)アルゴリズムの詳細説明

はじめに

バブルソートとは、大まかに言うと、隣接する 2 つの数値を順番に比較し、最後の 2 桁までの大きさに応じてソートすることです。仕分けの際、常に小さい数字が前方に、大きな数字が後方に配置されることになり、泡が上がっていくのと同じことになるため、バブルソートと呼ばれています。しかし実際には、必要に応じて、大木を前方に配置し、小数点を後方に配置することもできます。

実際の戦闘

コードに直接移動:

<?php
/**
 * 冒泡排序算法示例
 */

// 这里以一维数组做演示
$demo_array = array(23,15,43,25,54,2,6,82,11,5,21,32,65);

// 第一层for循环可以理解为从数组中键为0开始循环到最后一个
for ($i=0;$i<count($demo_array);$i++) {
    // 第二层将从键为$i的地方循环到数组最后
    for ($j=$i+1;$j<count($demo_array);$j++) {
        // 比较数组中相邻两个值的大小
        if ($demo_array[$i] > $demo_array[$j]) {
            $tmp            = $demo_array[$i]; // 这里的tmp是临时变量
            $demo_array[$i] = $demo_array[$j]; // 第一次更换位置
            $demo_array[$j] = $tmp;            // 完成位置互换
        }
    }
}

// 打印结果集
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
var_dump($demo_array);
echo &#39;

';

実行結果:

array(13) {
  [0]=>
  int(2)
  [1]=>
  int(5)
  [2]=>
  int(6)
  [3]=>
  int(11)
  [4]=>
  int(15)
  [5]=>
  int(21)
  [6]=>
  int(23)
  [7]=>
  int(25)
  [8]=>
  int(32)
  [9]=>
  int(43)
  [10]=>
  int(54)
  [11]=>
  int(65)
  [12]=>
  int(82)
}

上記の結果から、配列内のキー値の順序が変更され、ソートが成功していることがわかります。

上記のアルゴリズムが値のサイズに応じて配列内のキー値を小さい値から大きい値に並べ替える場合、逆に大きい値から小さい値へ演算するにはどうすればよいでしょうか?

非常に簡単で、次のように比較記号を変更するだけです:

<?php
/**
 * 冒泡排序算法示例
 */

// 这里以一维数组做演示
$demo_array = array(23,15,43,25,54,2,6,82,11,5,21,32,65);

// 第一层for循环可以理解为从数组中键为0开始循环到最后一个
for ($i=0;$i<count($demo_array);$i++) {
    // 第二层将从键为$i的地方循环到数组最后
    for ($j=$i+1;$j<count($demo_array);$j++) {
        // 比较数组中相邻两个值的大小
        if ($demo_array[$i] < $demo_array[$j]) {
            $tmp            = $demo_array[$i]; // 这里的tmp是临时变量
            $demo_array[$i] = $demo_array[$j]; // 第一次更换位置
            $demo_array[$j] = $tmp;            // 完成位置互换
        }
    }
}

// 打印结果集
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
var_dump($demo_array);
echo &#39;

';

実行結果:

array(13) {
  [0]=>
  int(82)
  [1]=>
  int(65)
  [2]=>
  int(54)
  [3]=>
  int(43)
  [4]=>
  int(32)
  [5]=>
  int(25)
  [6]=>
  int(23)
  [7]=>
  int(21)
  [8]=>
  int(15)
  [9]=>
  int(11)
  [10]=>
  int(6)
  [11]=>
  int(5)
  [12]=>
  int(2)
}

それだけで、簡単に順序を変更できます。

拡張

上記のコードをよく見ると、注意すべき点が 1 つあることがわかります。それは、スワップ変数です。はい、これはバブリングの核心でもあり、このテクニックをマスターすれば、将来的には他の場所でも使用できます。

ここで少しお話します。

原則:

今、2 つの変数 A と B があり、要件はそれらの値を交換することです。

タイトルを見ると直接代入を思い浮かべるかもしれませんが、直接代入すると誰が先に代入しても必ずどちらかが上書きされてしまいます。ここから3つ目の変数が考えられます。 C、必要な目標を達成できるように、A または B に値を一時的に保存します。

$c = $a; // 暂存
$a = $b; // b给a
$b = $c; // 暂存的a值再给b

注: 実際には、A 変数と B 変数の値を交換することも可能であり、substr() や str_replace() などのメソッドを使用することもできます。バブルソートを導入しているので、あまり拡張したくありません。

まとめ

バブルソートについてはたくさんありますが、まとめると、

ループ比較

キーの値を交換する

この2点ができれば基本的にはOKです。 、バブルソートについて 他にも多くのアルゴリズムがありますが、ここではそのうちの 1 つを紹介します。興味のある学生は自分で学習できます。