PHP算法大全(3)班长帮差生排队-选择排序法

2017-03-14 10:03:15 admin ...

前言

上一节我们讨论了利用冒泡排序让差生排队,这次我们使用另外一种办法排队-选择排序。

内容概要

1、什么是选择排序。

2、选择算法的动画图。

3、选择算法的PHP代码实现。

一、什么是选择排序。

书接上回。

老师不满意(对不起老师,剧情需要):你们换一种方式排队,班长,你来帮他们。

学生随机排序,位置标号为:ABCDE;一定要记住,这是位置的标号。

班长先问排在第一位A的同学,你多少分?然后,问出第二个同学B的分数,如果分数比第一个少的话,就让第二个同学与第一个同学互换位置;否则继续问第三位C的同学,如果第三位C同学比第一位A少的话,互换位置,否则继续……,如此一轮,第一位A位置排好了。

接着为第二位B,你的分数多少?然后问第三位C的分数,如果C位置同学分数少的话,互换位置,否则继续……如此一轮,第二位B的位置排好了。

……

这样经过5-1=4轮的询问成绩和互换位置,顺序就排好了。

也就是说:在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。这个排序的方法就叫做选择排序法。

二、选择算法的动画图。

和冒泡排序法的例子一样,我们假设ABCDE位置上的成绩分别是30, 49, 15, 21, 19;看下面的模拟动画。

三、选择算法的PHP代码实现

我们和上期一样,将学生构造成一个索引数组,其中索引表示值表示位置,数组元素是学生的成绩。

代码献丑如下:

<?php
/************************************************************
** @Description:  PHP排序算法之选择排序
** @Author: haodaquan
** @Date:   2017-03-13 12:16:22
** @Last Modified by:   haodaquan
** @Last Modified time: 2017-03-13 13:40:36
*************************************************************/

function selectSort($arr) {
    #双重循环完成,外层控制轮数,内层控制比较次数
    $len = count($arr);
    if ($len <= 1) return $arr;

    for($i=0; $i<$len-1; $i++) {
        #先假设最小的值的位置
        $p = $i;

        for($j=$i+1; $j<$len; $j++) {
            #$arr[$p] 是当前已知的最小值
            if ($arr[$p] <= $arr[$j]) continue;
            #比较,发现更小的,记录下最小值的位置;
            #并且在下次比较时采用已知的最小值进行比较。
            $p = $j;
        }
        #已经确定了当前的最小值的位置,保存到$p中。
        #如果发现最小值的位置与当前假设的位置$i不同,则位置互换即可。
        if($p == $i) continue;

        $tmp      = $arr[$p];
        $arr[$p] = $arr[$i];
        $arr[$i] = $tmp;
    }
    #返回最终结果
    return $arr;
}

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

运行结果我就不贴出来了,比较简单。

我在代码里加入了注释(其实我平时是不这么注释的),大家应该可以看懂,这里就赘述了。

虽然这些算法比较简单,估计大家看其他的资料也可以看懂,这里是我学习时的想法,能记忆得很久,面试基本不用复习这些基本算法,写出来供大家参考。

相似文章


345708673

在路上

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