当前位置:首页 > PHP教程 > php应用 > 列表

PHP简单选择排序算法实例

发布:smiling 来源: PHP粉丝网  添加日期:2021-05-09 14:50:50 浏览: 评论:0 

这篇文章主要介绍了PHP简单选择排序算法实例,本文直接给出实现代码,并以类的方式实现,需要的朋友可以参考下

简单的选择排序算法:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换,代码如下:

  1. <?php 
  2.     class Sort{ 
  3.         /** 
  4.          * 简单的选择排序 
  5.          * 
  6.          * @param unknown_type $arr 
  7.          */ 
  8.         public function selectSort(&$arr) { 
  9.             $len=count($arr); 
  10.             for ($i=0;$i<$len;$i++) { 
  11.                 $min=$i
  12.                 for ($j=$i+1;$j<=$len-1;$j++) { 
  13.                     if ($arr[$min]>$arr[$j]) {//如果找到比$arr[$min]较小的值,则将该下标赋给$min 
  14.                         $min=$j
  15.                     } 
  16.                 } 
  17.                 if ($min!=$i){//若$min不等于$i,说明找到了最小值,则交换 
  18.                     $this->swap($arr[$i],$arr[$min]); 
  19.                 } 
  20.             } 
  21.         } 
  22.         /** 
  23.          * 将$a和$b两个值进行位置交换 
  24.          */ 
  25.         public function swap(&$a,&$b) { 
  26.             $temp=$a
  27.             $a=$b
  28.             $b=$temp
  29.         } 
  30.     } 
  31.     $arr=array(4,6,1,2,9,8,7,3,5); 
  32.     $test=new Sort(); 
  33.     $test->selectSort($arr);//简单的选择排序 
  34. //    var_dump($arr); 
  35. ?> 

简单选择排序的特点:交换移动数据次数相当少,从而节约了相应的时间

简单选择排序的时间复杂度分析:

无论最好最差的情况,其比较次数都是一样多,第i趟排序需要进行n-i次关键字的比较,此时需要比较n(n-1)/2次。所以最终的时间复杂度是O(n^2),尽管与冒泡排序同为O(n^2),但选择排序的性能还是略优于冒泡排序的。

Tags: PHP排序算法

分享到: