PHP简单选择排序算法实例

前端之家收集整理的这篇文章主要介绍了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相关文章