您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

8-1 常见算法考察点

发布时间：2020-10-07 11:51:23编辑：雪饮阅读（）

冒泡排序

这是一个从小到大排序的冒泡排序算法

<?php
function myDump($val){
    echo "<pre>";
    print_r($val);
    echo "</pre>";
}
$arr=[2,3,4,7,5,8,1,0,6];
myDump($arr);
for($i=0,$c=count($arr);$i<$c-1;$i++){
    for($j=0;$j<$c-$i-1;$j++){
        $temp=$arr[$j];
        if($arr[$j]>$arr[$j+1]){
            $arr[$j]=$arr[$j+1];
            $arr[$j+1]=$temp;
        }
    }
}
myDump($arr);

解析：



总结：结合数组索引下标从0开始以及上面解析步骤的前两个步骤不难看出，每轮（每i）排序后都会将最大的数字甩到末尾，所以我们内部循环的时候条件就是小于i。

时间复杂度：

由于用了两个for循环，所以并且值是动态的不是固定的，所以时间复杂度为O(n^2)

关于时间复杂度请参考：http://www.gaojiupan.cn/xuewuzhijing/xindebiji/3231.html

空间复杂度：

虽然用了两个for循环，但是只用了一个临时变量，所以空间复杂度是O(1)

 

关于空间复杂度请参考：http://www.gaojiupan.cn/xuewuzhijing/xindebiji/3232.html