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获取网站域名和地址的代码

复制代码 代码如下:<? function PMA_getenv($var_name) { if (isset($_SERVER[$var_name])) { return $_S...

PHP实现单链表翻转操作示例

本文实例讲述了PHP实现单链表翻转操作。分享给大家供大家参考,具体如下: 当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。 这里给出了一个单链表的定义及翻转操作方法:...

centos下file_put_contents()无法写入文件的原因及解决方法

centos下file_put_contents()无法写入文件的原因是没有文件夹权限 直接修改目标文件夹/文件 # chmod 777 文件夹名称 以上这篇centos下file_pu...

详解PHP序列化反序列化的方法

经常看到一些配置文件里面存放的是一些类似带有格式的变量名称和值,其实就是一个序列化的过程,在需要用到这些数据库的时候会进行一个反序列化过程,就是将这个字符串再还原成他原来的数据结构。下面...

Discuz! 5.0.0论坛程序中加入一段js代码,让会员点击下载附件前自动弹出提示窗口

你需要修改attachment.php文件 在根目录下  在$attachexists = $ispaid = FALSE;下...