有你,世界才更有趣!

PHP写排序算法(一)冒泡排序

冒泡排序

依次比较相邻的两个元素,每次比较完毕最大的一个字跑到本轮的末尾。

例如:$arr=[26,76,43,41,86,1,45,49,71,4];

第一轮比较相邻两个元素,如果左边元素大于右边元素,则交换。 

26和76比较的结果就是,26在前,76在后; 
然后76和43比较的结果,43在前,76在后;
然后76和41比较的结果,41在前,76在后;
然后76和86比较的结果,76在前,86在后;
然后86和1比较的结果,1在前,86在后;
然后86和45比较的结果,45在前,86在后;
然后86和49比较的结果,49在前,86在后;
然后86和71比较的结果,71在前,86在后;
然后86和4比较的结果,4在前,86在后;

以此类推,第一轮比较之后的结果是:26,43,41,76,1,45,49,71,4,86。经过第一轮比较,最大的元素跑到了最后一个,所以第二轮比较,最后一个元素不需要进行比较了。  第三轮还是从索引0和1开始比较,最后两个不比较了。第四轮、第五轮以此类推。


$arr=[26,76,43,41,86,1,45,49,71,4];
// 冒泡排序
function maopao(array $arr) :array{
$len=count($arr);
for ($i=0; $i <$len ; $i++) {
# code...
for ($j=0; $j <$len-$i-1; $j++) {
# code...
if ($arr[$j]>$arr[$j+1]) {
# code...
$t=$arr[$j];
$arr[$j]=$arr[$j+1];
$arr[$j+1]=$t;
}
}
var_dump($arr);
}
return $arr;
}
var_dump(maopao($arr));

每次比较结果:

《PHP写排序算法(一)冒泡排序》
《PHP写排序算法(一)冒泡排序》
《PHP写排序算法(一)冒泡排序》
《PHP写排序算法(一)冒泡排序》

时间复杂度:

从代码中可以看出一共遍历了n-1 + n-2 + … + 2 + 1 = n * (n-1) / 2 = 0.5 * n ^ 2 – 0.5 * n,那么时间复杂度是O(N^2)。

稳定性:

因为arr[j]==arr[j+1]的时候,我们可以不移动arr[j]和arr[j++],所以冒泡排序是稳定的。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注