重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。
先附上冒泡排序的代码:
<?php // 冒泡排序 正序 function bubbleSort ( $arr ) { $count = count($arr); for ($i=1; $i < $count; $i++) { for ($j=0; $j < $count-$i; $j++) { if ($arr[$j] > $arr[$j+1]) { // 交换算法 // ---小->大---- // 先把小值 赋值给临时变量 $tmp = $arr[$j+1]; // 再把大值 赋值给小的值 $arr[$j+1] = $arr[$j]; // 再把临时变量(小值) 赋值给大值 $arr[$j] = $tmp; // 结论就是: 俩个值交换位置 小的值在左边, 大的值在右边. } } } return $arr; } $arr = [3,2,6,4,1,7,8,0,9]; var_dump(bubbleSort($arr));
如果没接触过,乍一看可能会愣一下,但是不要慌,且听我们的分析。
分析过程
我们用自我问答的方式讲解一下其中你可能会不理解的地方。
1、为什么外层的$i=1 ?
相信我, 这不是一个问题, 如果你改一改for循环的大于号小于号之类的, 你可以让他变成0或者任何数.
由于$j=0, 而且数组最后一位数是不需要$arr[$j]这样比较的, 因为他是最后一位. 假设数组长度是9,第一次循环$i就是12345678, $j就是01234567
2、为什么内层循环要有一个$count-$i ?
这其实是为了优化循环的次数, 如果你细心打印观察的话, 你就会发现, 当外层循环第一次循环结束后, 数组内的最大值, 必定在数组的最右边 (提供的代码是正序从小到大排的), 既然最大值已经在最右边了, 那不就可以内层循环的次数减去外层已经循环的次数了吗?
3、if里面的代码是什么 ?
注释的已经很清楚了, 用一个临时变量存储数据, 然后大值赋给小值, 小值赋给大值。
优化
此处转自文章: PHP实现排序算法----冒泡排序(Bubble Sort)
《大话数据结构》果然是本好书,还给我们介绍了冒泡排序算法的改进,这里我就直接搬它的陈述:
上面的冒泡排序算法是否还可以优化呢?答案是肯定的。试想一下,如果我们待排序的序列是{2,1,3,4,5,6,7,8,9},也就是说,除了第一和第二个关键字需要交换外,别的都已经是正常的顺序了。当 i = 0 时,交换了 2 和 1 ,此时的序列已经是有序的了,但是算法仍然不依不挠地将 i = 2 到 9 以及每个循环中的 j 循环都执行了一遍,尽管并没有交换数据,但是之后的大量比较还是大大地多余了。
当 i = 2 时,我们已经对 9 与 8,8 与 7,·······,3 与 2 做了比较,没有任何数据交换,这就说明此序列已经有序,不需要再继续后面的循判断工作了(后面的工作也是不会发生任何数据交换,再做也是没有意义了)。为了实现这个想法,我们需要改进一下代码,增加一个标记变量 flag 来实现这一算法的改进:
代码:
<?php // 冒泡排序 function bubbleSort ( $arr ) { $count = count($arr); $flag = TRUE; for ($i=1; ($i < $count) && $flag; $i++) { $flag = FALSE; for ($j=0; $j < $count-$i; $j++) { if ($arr[$j] > $arr[$j+1]) { // ---小->大---- // 先把小值 赋值给临时变量 $tmp = $arr[$j+1]; // 再把大值 赋值给小的值 $arr[$j+1] = $arr[$j]; // 再把临时变量(小值) 赋值给大值 $arr[$j] = $tmp; // 结论就是: 俩个值交换位置 小的值在左边, 大的值在右边. $flag = TRUE; } } } return $arr; } $arr = [3,2,6,4,1,7,8,0,9]; var_dump(bubbleSort($arr));
关注我们:请关注一下我们的微信公众号:扫描二维码

版权声明:本文为原创文章,版权归 木鱼 所有,欢迎分享本文,转载请保留出处!