一个phper,笔试,面试,技术栈的总结

powerby flight phpms

成功,唯有积累,没有奇迹

关于我

瞧一瞧,看一看:

吴大叔,20已过半,30还未满,175cm的个子,65kg的体重,平淡的就像差不多先生,一个非主流的程序员,目前的理想是赚钱,得一灵魂伴侣,然后隐居山水之间,蹦野迪

友情链接

一切只是开始,我从未放弃过改变

php 冒泡排序的两种思路以及优化

时间:2019-01-14 02:56:39

php冒泡排序,两种思路,时间复杂度都是O(n^2),当然最优的时间复杂度就是O(n),以下说的都是正序排列(倒序的话,把内层循环的大于号换成小于号就好了)

第一种冒泡排序

思路就是把第一个数跟所有的数比较,如果碰到比第一个数还小的数字,就把他俩位置交换下,然后把交换后的数字继续往后比较...

这样第一轮交换能得出什么呢,就是第一轮交换完,数组的第一个位置,一定是最小的数

循环体内,每次$j = $i + 1, 因为外层每循环一次已经把最小的数压到数字头部了, 没必要从头开始比较了

$numbers = array(-2, 5, 3, 1, -3, -4);
for ($i=0;$i<count($numbers);$i++) {
    for ($j=$i+1;$j<count($numbers);$j++) {
        if ($numbers[$i] > $numbers[$j]) {
            $tmp         = $numbers[$i];
            $numbers[$i] = $numbers[$j];
            $numbers[$j] = $tmp;
        }
    }
    // var_dump($numbers);
}
var_dump($numbers);exit;

第一轮交换的过程:拿数组的第一位-2跟5比,发现没有我小,跳过,拿-2跟3比,发小没有我小跳过...

拿-2跟-3比的时候,发小比我还小,两个交换下位置,下次循环的时候数组第一位已经发生了变化,是-3。嗯,仔细想想

然后循环还没完,继续拿数组的第一位(-3),跟数组最后一位-4比较,又交换下位置...

结果:[-4, 5, 3, 1, -2, -3]

第二轮循环时候拿5跟数组后面的开始比较,没必要跟前面的比了,因为经过上一轮的比较,第一位肯定是最小的...

第二种冒泡排序

思路就是一组一组数字(相邻的两个数)比较,如果大于后面的数字就发生交换,这样比较完的结果就是会把最大的数移动到最后的位置

$numbers = array(-2, 5, 3, 1, -3, -4);
for ($i = 0; $i < count($numbers); $i++) {
    for ($j = 0; $j < count($numbers) - $i - 1; $j++) {
        if ($numbers[$j] > $numbers[$j + 1]) {
            $temp = $numbers[$j];
            $numbers[$j] = $numbers[$j + 1];
            $numbers[$j + 1] = $temp;
        }
    }
    var_dump($numbers);
}

第一轮交换完过程就是: -2不大于5不交换,5大于3交换,5大于1交换,5大于-3交换,5大约-4交换....

结果: [-2, 3, 1, -3, -4,5] ...

第二轮交换的时候,注意条件$j < count($numbers) - $i - 1; 已经不跟最后一个比较了,因为你懂的...

关于优化

如果数组是: [5,1,2,3,4] 套用我们第二种思路的话, 是不是我们第一轮循环完(结果是[1,2,3,4,5]), 就可以终止循环了.

加个变量,如果里面没有发生交换,就意味着数组目前就是有序的,可以退出循环了

$numbers = [5,1,2,3,4];
for ($i = 0; $i < count($numbers); $i++) {
    $flag = 1;
    for ($j = 0; $j < count($numbers) - $i - 1; $j++) {
        if ($numbers[$j] > $numbers[$j + 1]) {
            $flag = 0;
            $temp = $numbers[$j];
            $numbers[$j] = $numbers[$j + 1];
            $numbers[$j + 1] = $temp;
        }
    }
    if($flag) break;
}
var_dump($numbers);exit;


 仅对管理员开放,支持markdown语法

有需要的,可以联系我 wuxiumu@163.com

Copyright © 2019. All rights reserved. 本站由 无朽木 纯手工打造