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中可以通过rmdir()函数删除一个空目录 <?php if (file_exis...

PHP5.3新特性小结

本文总结分析了PHP5.3新特性。分享给大家供大家参考,具体如下: 1、命名空间 解决了类,函数和常量名冲突的问题 2、静态绑定 继承时父类可以直接调用子类重写父类的方法 class...

php intval函数用法总结

语法: int intval ( $var, $base ) 参数: 此函数接受两个参数,其中一个是必需的,而另一个是可选的。 参数如下所述: $var:这是一个必需参数,用作需要...

php以fastCGI的方式运行时文件系统权限问题及解决方法

php以fastCGI的方式运行时文件系统权限问题及解决方法

今天准备将一个php demo放在IIS下运行,网站在IIS下的配置是这样的: 应用程序池是集成模式下的.net framework 2.0(2.0或4.0没什么关系,因为php以fas...

PHP读取文件,解决中文乱码UTF-8的方法分析

本文实例讲述了PHP读取文件,解决中文乱码UTF-8的方法。分享给大家供大家参考,具体如下: $opts = array( 'file' => array( 'en...