冒泡排序原理及PHP实现冒泡排序

1、冒泡排序原理

比较两个相邻元素之间值的大小，将值大的元素交换到右边。

2、为什么叫冒泡

向池塘中扔一块石头时会发现，扔石头的地方不断有气泡的往上冒，且越往上气泡越大。在程序中，通过比较两个值的大小，然后把最大的值放到右边，如同冒泡一样把最大值排到最后。

3、理解冒泡排序过程

等待排序的数据：$arraySort = [8,2,5,4];

从小到大排序

第一轮排序

第一次：2,8,5,4 8和2比较，8>2,8和2位置互换
第二次：2,5,8,4 8和5比较，8>5,8和5位置互换
第三次：2,5,4,8 8和4比较，8>4,8和4位置互换

第二轮排序 第一次：2,5,4,8 2和5比较，2<5，位置不变
第二次：2,4,5,8 5和4比较，5>4，位置互换

第三轮排序 第一次：2,4,5,8 2和4比较，2<4，位置不变

规律总结

对于一个长度为N的数组，需要排序 N-1 轮，每 i 轮 要比较 N-i 次。对此我们可以用双重循环语句，外层循环控制循环轮次，内层循环控制每轮的比较次数。

4、代码实现

$arraySort = [8,2,5,4];

function bubble_sort($arr){

    // 获取数组长度
    $arrayLength = count($arr);

    // 控制循环轮次数
    for($i=1; $i<$arrayLength; $i++){
        // 控制轮次下循环次数
        for($j=0;$j<$arrayLength-$i;$j++){
            // 比较两个相邻两个值的大小，如果当前值大于后面的值，则进行位置交换
            if($arr[$j] > $arr[$j+1]){
                // 位置互换，把大的值赋值给$tmp临时变量
                $tmp = $arr[$j];
                // 小值替换大值 
                $arr[$j] = $arr[$j+1];
                // 大值替换小值
                $arr[$j+1] = $tmp;
            }
        }
    }

    return $arr;
}

$arr = bubble_sort($arraySort);
print_r($arr);

代入程序循环理解

/*
[8,2,5,4]
第一轮循环
i = 1
    $j = 8 , $j+1 = 2
        $tmp = $j = 8;
        $j = $j+1 = 2;
        $j+1 = 8;
    2,8,5,4

    $j = 8 , $j+1 = 5
        $tmp = $j = 8;
        $j = $j+1 = 5
        $j+1 = 8
    2,5,8,4

    $j = 8 , $j+1 = 4
    $tmp = $j = 8;
    $j = $j+1 = 4;
    $j+1 = 8;
    2,5,4,8
*/

我是夕阳何处寻，期待和优秀的你一起同行!

夕阳何处寻

2020年04月04日