基础算法（枚举、递归、二分、归并、快速） php

什么是算法

数据元素之间的关系有逻辑关系和物理关系，对应的运算有基于逻辑结构的运算描述和基于存储结构的运算实现。

通常把基于存储结构的运算实现的步骤或过程称之为算法。

算法的五个重要的特性

 有穷性：在有穷步之后结束，算法能够停机。
 确定性：无二义性。
 可行性：可通过基本原酸有限次执行来实现，也就是算法中每一个动作能够被机械地执行。
 有输入。
 有输出。

枚举：

枚举就是将所有的结果进行尝试计算。

优化的思路

 循环的时候，根据 所需要的顺序，进行循环，将一些不需要的结果省去循环时间。

 

eg ：

• 形如a^3= b^3 + c^3 + d^3的等式被称为完美立方等式。例如

123= 63 + 83 + 103 。编写一个程序，对任给的正整数N (N≤100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 + c3 + d3，其中a,b,c,d 大于1, 小于等于N，且b<=c<=d。

• 输入

一个正整数N (N≤100)。

• 输出

每行输出一个完美立方。输出格式为： Cube = a, Triple = (b,c,d)

其中a,b,c,d所在位置分别用实际求出四元组值代入。

解题思路：

1. a枚举的范围是[2,N]

2. b枚举的范围是[2,a-1]

3. c枚举的范围是[b,a-1]

4. 1. a枚举的范围是[2,N]

   2. b枚举的范围是[2,a-1]

   3. c枚举的范围是[b,a-1]

   4. b枚举的范围是[c,a-1]

       定义 $a,$b,$c,$d
       function meiju(){
           $array = [];
         for($a=2;$a<=$N;$a++){
          for($b=2;$b<=$a-1;$b++){
           for($c=$b;$c<=$a-1;$c++){
            for($d=$c;$d<=$a-1;$d++){
             if($a*$a*$a==$b*$b*$b+$c*$c*$c+$d*$d*$d){
              $array[] = [$a,$b,$c,$d];
             }
            }
           }
          }
         }
         return $array;
       }

递归

递归就是自己调用自己。

递归的作用 ：

1. 替代多重循环。

2. 解决本来就是用递归形式定义的问题。

3. 将问题分解为规模更小的子问题进行求解。

二分算法

将 数组进行中间分开 每次查找是原来的1/2的数据量。

eg：

 输入: nums = [-1,0,3,5,9,12], target = 9
 输出: 4
 解释: 9 出现在 nums 中并且下标为 4

 function search($nums, $target) {
      if(!is_array($nums) && empty($nums)){
          return -1;
      }
      $heid = count($nums)-1;//查找的最右边
      $lowr = 0; //查找的最左边
      while($lowr <= $heid){ // 查询区间
          $middle = intval($lowr+($heid-$lowr)/2); // 找出中间值  $heid-$lowr防止数据太大，内存溢出
          if($nums[$middle] > $target){
          $heid = $middle - 1; //设置最右边
          }else if($nums[$middle] < $target){
          $lowr = $middle + 1; //设置最左边
          }else{
          return $middle;
          }
      }
      return -1; 
  }

归并排序

使用了分治的思想 将一个数组进行分开，分别对两个数组进行排序，再将数组重组

 输入 ： [9,5,4,2,1,4,8,96,12,0,5,4,8,6,74]
 输出 ： 0,1,2,4,4,4,5,5,6,8,8,9,12,74,96

 function msort(&$arr,$low,$high){
  if($low<$high){
      $mid = floor(($low+$high)/2);
      msort($arr, $low, $mid);
      msort($arr,$mid+1,$high);
      mergeArray($arr,$low,$mid,$high);
  }
 }
 ?
 function mergeArray(&$arr,$low,$mid,$high){
  $i = $low;
  $j = $mid+1;
 ?
  while($i<=$mid && $j<=$high){
      if($arr[$i]<$arr[$j]){
          $tmp[] = $arr[$i++];
      }else{
          $tmp[] = $arr[$j++];
      }
 }
 ?
 while($i<=$mid){
      $tmp[] = $arr[$i++];
  }
  while($j<=$high){
      $tmp[] = $arr[$j++];
  }
  $len = count($tmp);
  for($k=0;$k<$len;$k++){
      $arr[$low+$k] = $tmp[$k];
  }
 }

快速排序

1. 从数组中取出一个数作为基准数。

2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3. 再对左右区间重复第二步，直到各区间只有一个数。

 输入 ： [9,5,4,2,1,4,8,96,12,0,5,4,8,6,74]
 输出 ： 0,1,2,4,4,4,5,5,6,8,8,9,12,74,96

 function quick_sort($my_array)
 {
     //定义两个中间值
     $loe = $gt = array();
     if (count($my_array) < 2) {
         return $my_array;
     }
     $pivot_key = key($my_array);
     $pivot = array_shift($my_array);
     foreach ($my_array as $val) {
         if ($val <= $pivot) {
             $loe[] = $val;
         } elseif ($val > $pivot) {
             $gt[] = $val;
         }
     }
     return array_merge(quick_sort($loe), array($pivot_key => $pivot), quick_sort($gt));
 }