PHP算法大全(2)冒泡排序算法解决差生排序问题

2017-03-11 12:14:10 admin ...

前言

算法是有用的,也是枯燥的,我们尽量用生活中的例子来描述。排序算法是算法中最基础的部分,今天我们一起来排序算法中的冒泡排序算法。

内容概要:

1、什么是冒泡算法-差生排序问题。

2、冒泡算法的动画图。

3、冒泡算法的PHP代码实现。

一、什么是冒泡算法-差生排序问题。

时光回到你上小学的时候某日,老师大怒:这次数学考试平均分在不及格的,站到讲台前来!5个同学不情愿的,慢吞吞的走到讲台前,他们随机的站成一排。

老师说:按照你们的成绩从小到大站成一排!

假设这五位同学的位置分别是ABCDE,他们相互不知道对方成绩,只能现场问旁边的同学。

使用美帝的小朋友补充一下画面

现实排序情况是比较乱的,站来站去,排队很长时间。

这时候冒泡排序算法就能帮上忙了。

首先说明一下:ABCDE是位置编号,排序的时候,我们不关心同学的名字,只关心某个位置上站的同学分数合适就行。

顺序是这样的,首先 A位置的同学和B位置的同学先相互问对方成绩,如果后者成绩小(差),他俩换一下位置,否则别动。同理,再比较B和C位置的同学成绩,如果C位置同学成绩小(差),就互换。依次再比较C和D、D和E位置的同学,

这样比较一轮,做的结果是ABCDE五个位置的同学两两比较了一次,这样做的结果有两个:

一是,每次两两位置比较,较差成绩的总会向前排一位,

二是,最好成绩的同学排到了合适位置(最后位置E)。

同理再来一轮比较,结果还是会将较差成绩的同学位置向前排一位,成绩第二好的同学会排到合适位置(D位置)不同的是,我们这次只需要比较ABCD四个位置就行了。

继续按照一轮一轮的比下去,会有条不紊的完成老师的排队要求的。

我们计算一下需要比多少轮:

第一轮:ABCDE

第二轮:ABCD

第三轮:ABC

第四轮:AB

也就是会比较4轮就可以完成要求了。

这就是冒泡排序。书面语言我就不抄了,大家自行搜索。

虽然比较啰嗦,但是我觉得我讲清楚了,不知大家是否清楚?请在评论中给个意见吧,感谢支持PHP在路上。

二、冒泡算法的动画图。

我们假设ABCDE位置上的成绩分别是30, 49, 15, 21, 19;看下面的模拟动画。

【具体这个动画图是怎么制作的,如果想知道的话,就在评论中告诉我哈。】

冒泡排序算法动画示意图

三、冒泡算法的PHP代码实现

PHP代码的实现是使用数组的方式,这里需要理解两点:

1、数组的下标就相当于我们例子中的ABCDE位置的概念。

2、数组的元素就是考试的成绩。

需要明确的是,例子中,我们实质上是按照成绩来排序的,千万不要说同学理解成数组的下标,否则会糊涂。

我也贴出来自己写的PHP冒泡排序算法。

<?php
/************************************************************
** @Description: PHP排序算法之冒泡算法
** @Author: haodaquan
** @Date:   2017-02-22 22:48:52
** @Last Modified by:   haodaquan
** @Last Modified time: 2017-03-13 12:16:11
*************************************************************/
function bubbleSort($arr)
{
    $len = count($arr);
    #该层循环控制 需要冒泡的轮数
    for($i = 1; $i < $len; $i++)
    { 
        #该层循环用来控制每轮 冒出一个数 需要比较的次数=元素数量-1
        for($k = 0; $k < $len-$i; $k++)
        {
            if($arr[$k] > $arr[$k+1])
            {
                #定义一个临时变量,交换位置使用
                $tmp        = $arr[$k+1];
                $arr[$k+1]    = $arr[$k];
                $arr[$k]    = $tmp;
            }
        }
    }
    return $arr;
}

#应用
$arr = [30,49,15,21,19];
var_dump(bubbleSort($arr));

运行结果就不贴出来了,和上面的动画图的结果是一样的。

冒泡排序比较简单,但面试和或笔试的时候,也会偶尔出现。而在实际的php程序开发过程中,是不需要写。

相似文章


345708673

在路上

技术无止境,一直在路上。 年过而立,惴惴不安,愈加发奋,孜孜求学。