PHP简单选择排序算法实例

yipeiwu_com5年前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中多维数组按指定value排序的实现代码

呵呵,业务需要按多维数组中某个元素进行排序,在PHP中也是非常容易实现的,一个函数调用一个回调函数就搞定了。贴出代码: 复制代码 代码如下: $arr = array( &nb...

PHP使用GD库输出汉字的方法【测试可用】

PHP使用GD库输出汉字的方法【测试可用】

本文实例讲述了PHP使用GD库输出汉字的方法。分享给大家供大家参考,具体如下: 一、原理 PHP中的GD库支持中文,但是必须要以UTF-8格式的参数来进行传递。下面先说一下汉字的UTF-...

PHP数组排序函数合集 以及它们之间的联系分析

下边提到的几个数组函数的排序有一些共性:1 数组被作为排序函数的参数,排序以后,数组本身就发生了改变,函数的返回值为bool类型。2 函数名中出现单a表示association,含义为,...

不错的dedecms修改实用集锦第1/2页

采集去除链接 复制代码 代码如下:{dede:trim}<a ([^>]*)>([^<]*)</a>{/dede:trim} ——...

php字符串分割函数用法实例

本文实例讲述了php字符串分割函数用法。分享给大家供大家参考。具体分析如下: php中explode 和 split 函数用来分割字符串。 explode函数语法如下 explode...