PHP简单选择排序算法实例_php技巧

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

<br /><?php<br />    class Sort{ <br />        /**<br />         * 简单的选择排序<br />         * <br />         * @param unknown_type $arr<br />         */<br />        public function selectSort(&$arr) { <br />            $len=count($arr);<br />            for ($i=0;$i<$len;$i++) {<br />                $min=$i;<br />                for ($j=$i+1;$j<=$len-1;$j++) {<br />                    if ($arr[$min]>$arr[$j]) {//如果找到比$arr[$min]较小的值，则将该下标赋给$min<br />                        $min=$j;<br />            <strong style="color:transparent">￥本文来源gaodai#ma#com搞@@代~&码网^</strong><small>搞gaodaima代码</small>        }<br />                }<br />                if ($min!=$i){//若$min不等于$i，说明找到了最小值，则交换<br />                    $this->swap($arr[$i],$arr[$min]);<br />                }<br />            }<br />        }<br />        /**<br />         * 将$a和$b两个值进行位置交换<br />         */<br />        public function swap(&$a,&$b) {<br />            $temp=$a;<br />            $a=$b;<br />            $b=$temp;<br />        }<br />    }<br />    $arr=array(4,6,1,2,9,8,7,3,5);<br />    $test=new Sort(); <br />    $test->selectSort($arr);//简单的选择排序<br />//    var_dump($arr);<br />?><br />

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

喜欢 (0)赏

[搞代码]

分享 (0)