php实现的几种基本的算法

写在这里的每个算法都会分析时间复杂度

1.冒泡排序

/*
  冒泡排序(效率比较低)

  外层循环决定循环层数
  内层,两两比较,交换位置
  每层循环过后,后面的值总是有序的最大(最小)的值,下次就无需去比较他们.
  加入变量flag,如果没有交换位置,则说明顺序是对的,可以跳出循环结束了.
*/

  $array=array();
  $array=array(1,98,5,34,23,87,54,23,12,0,456,123,45);
  $length=count($array);

  for($i=1;$i$array[$j+1]){
              $flag=true;
              $temp =$array[$j];
              $array[$j]=$array[$j+1];
              $array[$j+1]=$temp;
          }
      }
      
      if($flag){
            break;
      }
  }

该排序算法效率较低, 

算法的时间复杂度为O(n^2)

2.选择排序

/*
  选择排序(比冒泡效率高)

    外层决定循环层数
    选择排序就是默认当前值为最小值,记录下标,然后进行循环比较,记录最小(最大值)的下标,最后交换两者的值.这样第一个值就是最小(最大)值.
    然后依次循环下去,最后得到的就是有序的数组.
*/

   $array=array();
   $array=array(1,98,5,34,23,87,54,23,12,0,456,123,45);
   $length=count($array);
   for($i=0;$i<$length-1;$i++)
   {
        $p=$i;  //默认当前位置的值为最小,记录最小下标.
        for($j=$p+1;$j$array[$j]){
                $p =$j; //如果当前值比默认值小,记录下标
           }
        }

        if($p !=$i){
           $temp=$array[$p];
           $array[$p]=$array[$i];
           $array[$i]=$temp;
        }
   }

3.快速排序(20世纪十大排序方法之一)

/*
   快速排序

   首先取一个值,作为标尺,把大于他的放到right_array中,小于他的放到left_array中,递归调用直到数组数为1,则返回,最后合并起来就是结果.
*/

    public function demo()
    {
        $array=array(1,98,5,34,23,87,54,23,12,0,456,123,45);

        $result=$this->quick_sort($array);

        var_dump($result);
    }

    //php
    public function quick_sort($array)
    {

      //先判断是否需要继续进行
      $length=count($array);
      if($length<=1){
          return $array;
      }

      //如果没有返回,说明数组内的元素个数 多余1个,需要排序
      //选择一个标尺
      //选择一个元素
      $base_num=$array[0];
      //遍历 除了标尺外的所有元素,按照大小关系放入两个数组内
      //初始化两个数组
      $left_array=array();//小于标尺的
      $right_array=array();//大于标尺的
      for($i=1;$i<$length;$i++)
      {
            if($base_num >$array[$i]){
                //放入左边数组
                array_push($left_array,$array[$i]);
            }else{
                //放入右边的数组
                array_push($right_array,$array[$i]);
            }
      }

      //再分别对左边和右边的数组进行相同的排序处理方式
      //递归调用这个函数 并记录结果
      $left_array=$this->quick_sort($left_array);
      $right_array=$this->quick_sort($right_array);

      //合并左边 标尺 右边
      return array_merge($left_array,array($base_num),$right_array);
    }

日记本

如果觉得我的文章对您有用,请随意赞赏。您的支持将鼓励我继续创作!

赞赏支持
被以下专题收入,发现更多相似内容