PHP简单选择排序算法实例

yipeiwu_com6年前PHP代码库

简单的选择排序算法:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换

复制代码 代码如下:

<?php
    class Sort{
        /**
         * 简单的选择排序
         *
         * @param unknown_type $arr
         */
        public function selectSort(&$arr) {
            $len=count($arr);
            for ($i=0;$i<$len;$i++) {
                $min=$i;
                for ($j=$i+1;$j<=$len-1;$j++) {
                    if ($arr[$min]>$arr[$j]) {//如果找到比$arr[$min]较小的值,则将该下标赋给$min
                        $min=$j;
                    }
                }
                if ($min!=$i){//若$min不等于$i,说明找到了最小值,则交换
                    $this->swap($arr[$i],$arr[$min]);
                }
            }
        }
        /**
         * 将$a和$b两个值进行位置交换
         */
        public function swap(&$a,&$b) {
            $temp=$a;
            $a=$b;
            $b=$temp;
        }
    }
    $arr=array(4,6,1,2,9,8,7,3,5);
    $test=new Sort();
    $test->selectSort($arr);//简单的选择排序
//    var_dump($arr);
?>

简单选择排序的特点:交换移动数据次数相当少,从而节约了相应的时间
简单选择排序的时间复杂度分析:
无论最好最差的情况,其比较次数都是一样多,第i趟排序需要进行n-i次关键字的比较,此时需要比较n(n-1)/2次。所以最终的时间复杂度是O(n^2)
尽管与冒泡排序同为O(n^2),但选择排序的性能还是略优于冒泡排序的。

相关文章

PHP简单装饰器模式实现与用法示例

本文实例讲述了PHP简单装饰器模式实现与用法。分享给大家供大家参考,具体如下: <?php //装饰器模式-在不改变原有类的结构上,对类的功能那个作补充 //武器基类...

php中Ctype函数用法详解

本文实例分析了php中Ctype函数用法。分享给大家供大家参考。具体分析如下: Ctype函数是Php的Ctype扩展函数提供了一组函数用于校验字符串中的字符是否是正确的格式,这里我们主...

eAccelerator的安装与使用详解

一、PHPeAccelerator安装去https://github.com/eaccelerator/eaccelerator/downloads下载最新版安装包,解压安装包,进入解压...

PHP面向接口编程 耦合设计模式 简单范例

复制代码 代码如下: <?php interface js{ function ys($a,$b); } class Af implements js{ function ys($...

php 删除数组元素

如果没有提供 callback 函数,array_filter() 将删除 input 中所有等值为 FALSE 的条目。 删除数组中为空值的元素就可以使用这个函数。 复制代码 代码如下...