找回密码
 注册加入

扫一扫,极速登录

QQ登录

只需一步,快速开始

搜索
查看: 6225|回复: 0

php之冒泡法排序

[复制链接]
TA的专栏
发表于 2012-12-16 16:26:03 | 显示全部楼层 |阅读模式
  1.      class Sort{
  2.          /**
  3.           * 简单的交换排序
  4.           * 冒泡排序初级版
  5.           * 这个不算是标准的冒泡排序算法,因为不满足“两两比较相邻记录”的冒泡排序思想,她更应该是最最简单的交换排序而已
  6.           * 思路:让每一个关键字和她后面的“每一个”关键字比较,如果大则交换
  7.           * 缺点:效率很低
  8.           */
  9.          public function bubbleSort1(&$arr){
  10.              $len=count($arr);
  11.              for ($i=0;$i<$len;$i++) {
  12.                  for ($j=$i+1;$j<$len;$j++){
  13.                      if ($arr[$i]>$arr[$j]) {///这里让每一个关键字和她后面的“每一个”关键字都进行比较
  14.                          $this->swap(&$arr[$i],&$arr[$j]);   
  15.                      }
  16.                  }
  17.              }
  18.          }
  19.          /**
  20.           * 正宗的冒泡排序算法
  21.           * 思路:通过“两两比较相邻记录”,从而将最小的值排到最顶端
  22.           */
  23.          public function bubbleSort2(&$arr){
  24.              $len=count($arr);
  25.              for ($i=0;$i<$len;$i++){
  26.                  for($j=$len-1;$j>$i;$j--) {//$j是从后往前循环
  27.                      if($arr[$j]<$arr[$j-1]) {//注意:这里是“两两比较相邻记录”,以bubbleSort1不同
  28.                          $this->swap(&$arr[$j],&$arr[$j-1]);//这里使用“引用”操作符
  29.                      }
  30.                  }
  31.              }
  32.          }
  33.          /**
  34.           * 冒泡排序算法的改进
  35.           * 如果要排序的数组是:[2,1,3,4,5,6,7,8,9]的话,其实只需要将1和2进行比较交换即可,后面的循环中的第二个for循环无需执行,但是如果使用bubbleSort2的话
  36.           * 照样会将$i=2到9及后面的for循环都执行一遍,这些比较明显是多余的
  37.           * 改进思路:在i变量的for循环中,增加了对flag是否为true的判断
  38.           */
  39.          public function bubbleSort3(&$arr){
  40.              $len=count($arr);
  41.              $flag=true;
  42.              for ($i=0;$i<$len && $flag;$i++){//如果之前的一次循环判断中,都没有进行数据交换,则表明目前的数据已经是有序的了,从而跳出循环
  43.                  $flag=false;
  44.                  for($j=$len-1;$j>$i;$j--) {//$j是从后往前循环
  45.                      if($arr[$j]<$arr[$j-1]) {//注意:这里是“两两比较相邻记录”,以bubbleSort1不同
  46.                          $this->swap(&$arr[$j],&$arr[$j-1]);//这里使用“引用”操作符
  47.                          $flag=true; //如果有数据交换,则将$flag设为true
  48.                      }
  49.                  }
  50.              }
  51.          }
  52.          /**
  53.           * 将$a和$b两个值进行位置交换
  54.           */
  55.          public function swap($a,$b) {
  56.              $temp=$a;
  57.              $a=$b;
  58.              $b=$temp;
  59.          }
  60.      }
  61.      $arr=array(4,6,1,2,9,8,7,3,5);
  62.      $test=new Sort();
  63. //    $test->bubbleSort1($arr);//简单的交换排序
  64. //    $test->bubbleSort2($arr);//冒泡排序
  65.      $test->bubbleSort3($arr);//改进后的冒泡排序
  66. ?>
复制代码

分析一下它的时间复杂度。

当最好的情况,也就是要排序的表本身就是有序的,那么我们比较次数,根据最后改进的代码,可以推断出就是n‐1次的比较,没有数据交换,时间复杂度为O(n)。

当最坏的情况,即待排序表是逆序的情况,此时需要比较 2012070815323628.png 次,并作等数量级的记录移动。因此,总的时间复杂度为O(n^2)。


转自:http://www.cnblogs.com/hongfei/archive/2012/07/08/2581583.html


您需要登录后才可以回帖 登录 | 注册加入  

本版积分规则

Archiver|手机版|小黑屋|Discuz!扩展中心 ( 浙ICP备14042422号-1 )|网站地图QQ机器人

GMT+8, 2024-3-29 07:01 , Processed in 0.402420 second(s), 16 queries , Gzip On, Redis On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表