PHP实现-冒泡排序


常见的排序算法有:冒泡排序,快速排序,选择排序,插入排序,本文对冒泡排序做了一个总结。

思路分析

想象一个大水池里有N多还未排好的序列的氢气球,较大的先冒出来,然后依次是较小的往上冒。即,每次比较相邻的两个数,小的在前大的在后,否则进行位置互换。

/**
  * 交换方法
  * @param array $arr 目标数组
  * @param $a 索引a
  * @param $b 索引b
  * @param bool $flag 交换标志
  * @return bool
  */
 function swap(array &$arr,$a,$b,$flag = false){
     // 遍历i后面的元素,只要该元素小于当前元素,就把较小的往前冒泡
     if($arr[$a] > $arr[$b]){
         $temp = $arr[$a];
         $arr[$a] = $arr[$b];
         $arr[$b] = $temp;
         $flag = true;
     }
     return $flag;
 }
 /**
  * 第一种写法
  * @param $arr 所要排序的数组
  * @return mixed 返回的数组
  */
 function bubbleSort($arr) {
     $len = count($arr);
     if ($len <= 1) {return $arr;}
     //该层循环控制 需要冒泡的轮数
     for ($i = 0; $i < $len-1; $i++) {
         //该层循环用来控制每轮 冒出一个数 需要比较的次数
         for ($j = $i + 1; $j < $len; $j++) {
             // 或者 $this->swap($arr,$j,$j+1);
             $this->swap($arr,$i,$j);
         }
     }
     return $arr;
 }
 //第二种写法
 public function BubbleSort2($arr){
     $len = count($arr);
     if ($len <= 1) {return $arr;}
     for ($i = 0;$i < $len-1;$i++){
         //TODO 本趟排序开始前,交换标志应为假
         $flag = false;
         for ($j = 0;$j <= $len-2;$j++){
             $flag = $this->swap($arr,$j,$j+1,$flag);
         }
         if(!$flag) return $arr;
     }
     return $arr;
 }
 //第三种写法
 function BubbleSort3(array &$arr){
     $len = count($arr);
     if ($len <= 1) {return $arr;}
     for($i = 0;$i < $len-1;$i++){
         //从后往前逐层上浮小的元素 $j >= 0
         for($j = $len - 2;$j >= $i ;$j --){
             $this->swap($arr,$j,$j+1);
         }
     }
     return $arr;
 }
 //第四种写法
 function bubbleSort4($arr)
 {
     $len = count($arr);
     if ($len <= 1) {return $arr;}
     for($i = 0;$i < $len-1;$i++) {
         for($j = 0;$j < $len-$i-1;$j++) {
             $this->swap($arr,$j,$j+1);
         }
     }
     return $arr;
 }

小结:

时间复杂度:O(n^2)

空间复杂度:O(1)

补充:可使用PHP内置函数 sort()或rsort().

上述函数对索引数组按照键值进行排序,为 array 中的单元赋予新的键名,这将删除原有的键名而不仅是重新排序。如果成功则返回 TRUE,否则返回 FALSE


冒泡排序属于稳定排序

上一篇 下一篇

评论

登录后可发表评论