PHP简单选择排序算法实例

yipeiwu_com7年前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多线程类及用法。分享给大家供大家参考。具体分析如下: 一般来说可通过WEB服务器来实现PHP多线程功能,当然,对多线程有深入理解的人都知道通过WEB服务器实现的多线程...

Ubuntu中支持PHP5与PHP7双版本的简单实现

前言 最近在编写一个工具的时候,使用了PHP命名空间特性,在命名空间中如果想引用常量、函数,需要PHP5.6以上的版本,但我阿里云 ECS 上安装的版本是PHP 5.5.9,由于 ECS...

Windows下的PHP 5.3.x安装 Zend Guard Loader教程

从PHP5.3开始如果要支持ZendGuard加密的PHP代码,必须安装Zend Guard Loader,老的zend optimizer将不被支持。另外,Zend Guard Loa...

PHP实现从上往下打印二叉树的方法

本文实例讲述了PHP实现从上往下打印二叉树的方法。分享给大家供大家参考,具体如下: 问题 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 解决思路 每层树从左到右打印,所以需要将...

php生成SessionID和图片校验码的思路和实现代码

/****** 产生Session ID ******/ 基本的思路: 是把当前微秒的时间获取, 然后产生以个随机数字, 把随机数字和当前时间相加后加密一下, 最后再截取需要的长度...