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 $demo_array[$j]) {            $tmp            = $demo_array[$i]; // 这里的tmp是临时变量
            $demo_array[$i] = $demo_array[$j]; // 第一次更换位置
            $demo_array[$j] = $tmp;            // 完成位置互换
        }
    }
}// 打印结果集echo '';
var_dump($demo_array);echo '';

実行結果:

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 '';
var_dump($demo_array);echo '';

実行結果:

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

注: 実際、3 番目の変数は必要ありません。substr()、str_replace() などのメソッドを使用して、A 変数と B 変数の値を交換することもできます。ここではバブルソートを紹介しているので、これはあまり拡張ではありません。

まとめ

バブルソートにはたくさんありますが、まとめると次の 2 つの主要なポイントがあります:

• ループ比較

• この 2 つのポイントを完了できれば、もちろん、バブルソートのアルゴリズムは他にもたくさんありますが、興味のある方はそのうちの 1 つを自分で学習してください。