Detailed explanation of PHP bubble sort (Bubble Sort) algorithm

Foreword

Bubble sorting roughly means comparing two adjacent numbers in sequence, and then sorting according to size until the last two digits. Since in the sorting process, small numbers are always placed forward and large numbers are placed backward, which is equivalent to bubbles rising, so it is called bubble sorting. But in fact, in the actual process, you can also use it in reverse according to your own needs. The big trees are placed forward and the decimals are placed backward.

Actual combat

Go directly to the code:

<?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;

';

Running result:

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)
}

From the above results, we can see that the order of the key values ​​in the array has been changed and the sorting is successful.

If the above algorithm is to sort the key values ​​​​in the array from small to large according to the value size, then how to operate from large to small in reverse?

It’s very simple, just modify a comparison symbol, as follows:

<?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;

';

Run result:

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)
}

That’s it, change the order easily.

Extension

If you look closely at the above code, you will find that there is one thing worth paying attention to, that is, the swap variable. Yes, this is also the core point of bubbling. Once you master this technique, you can also use it in other places in the future.

Here we will talk about this a little bit.

Principle:

Now there are two variables A and B, and the requirement is to interchange their values.

When we see the title, we may first think of direct assignment, but if we assign directly, no matter who is assigned to whom first, one of them will definitely be overwritten. From this, we can come up with a third variable C, temporarily Store the value in A or B so that the required goal can be achieved.

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

Note: In fact, there is no need for a third variable, and the values ​​of A and B variables can be interchanged. You can use methods such as substr(), str_replace(), etc. This is because we are introducing bubble sorting, so we don’t want to extend it too much. .

Summary

There are so many things about bubble sorting. To sum up, there are two main points:

Loop comparison

Exchange key values

If you can complete these two points, it is basically OK. Of course, about bubble sorting There are many other algorithms, here is just one of them, interested students can study it by themselves.