理解
冒泡排序,时间复杂度哦、O(N^2)
冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是 O(N 2)。这是一个非常高的时间复杂度。冒泡排序早在 1956 年就有人开始研究,之后有很多人都尝试过对冒泡排序进行改进,但结果却令人失望。如 Donald E. Knuth(中文名为高德纳, 1974 年图灵奖获得者)所说:“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外,似乎没有什么值得推荐的。”
代码实现
<?php
/**
* Created by PhpStorm.
* User: benny
* Date: 18-11-20
* Time: 下午4:21
*/
/**
* @param $array
*/
function bubble_sort($array){
$count = count($array);
var_dump($count);
echo "<br/>";
print_r($array);
echo "<br/>";
for ($i=1;$i<=$count-1;$i++){ //$count个数,需要冒泡$count-1唐
for ($j=0;$j<$count-$i;$j++){ //$i为已经进行的次数,保证最后($count-$i)位为最大(小)位,无需进行
if ($array[$j]>$array[$j+1]){
$temp = $array[$j];
$array[$j] = $array[$j+1];
$array[$j+1] = $temp;
}
}
}
print_r($array);
}
bubble_sort([1,28,3,4,6,9,76,2,4]);
网友评论