PHP常用的排序和查找算法详解

本教程讲解PHP常用的排序和查找算法详解

具体代码如下：

<?php /**  * PHP最常用的四个排序方法及二种查找方法  * 下面的排序方法全部都通过测试  * auther : soulence  * date : 2015/06/20  */    //PHP冒泡排序法 function bubbleSort(&$arr){  //这是一个中间变量  $temp=0;  //我们要把数组，从小到大排序  //外层循环  $flag=false;//这个优化之后效率会很高，一般够用  for($i=0;$i<count($arr)-1;$i++){        for($j=0;$j<count($arr)-1-$i;$j++){      //说明前面的数比后面的数大，就要交换      if($arr[$j]>$arr[$j+1]){         $temp=$arr[$j];         $arr[$j]=$arr[$j+1];         $arr[$j+1]=$temp;         $flag=true;      }    }    if(!$flag){     //已经是有序了     break;    }    $flag=false;   } }    //PHP选择排序法  效率比冒泡要高 function selectSort(&$arr){   $temp=0;   for($i=0;$i<count($arr)-1;$i++){     //假设$i就是最小的数     $minVal=$arr[$i];     //记录我认为的最小数的下标     $minIndex=$i;     for($j=$i+1;$j<count($arr);$j++){       //说明我们认为的最小值，不是最小       if($minVal>$arr[$j]){          $minVal=$arr[$j];          $minIndex=$j;       }     }     //最后交换     $temp=$arr[$i];     $arr[$i]=$arr[$minIndex];     $arr[$minIndex]=$temp;   } }    //插入排序法(小到大排序)  效率又比 选择排序法要高一些 function insertSort(&$arr){   //先默认下标为0的这个数已经是有序   for($i=1;$i<count($arr);$i++){     //$insertVal是准备插入的数     $insertVal=$arr[$i];     //准备先和谁下标为$inserIndex的比较     $inserIndex=$i-1;     //如果这个条件满足，说明我们还没有找到适当的位置     while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){     //同时把数后移       $arr[$inserIndex+1] = $arr[$inserIndex];       $inserIndex--;     }     //插入（这时就给$inserIndex找到适当的位置）     $arr[$inserIndex+1] = $insertVal;   } }        //快速排序法 第一种写法 不是我实现的 function quickSort($left,$right,&$arr){    $l=$left;    $r=$right;    $pivot= $arr[($left+$right)/2];    while($l<$r){      while($arr[$l]<$pivot){       $l++;      }      while($arr[$r]>$pivot){       $r--;      }      if($l>=$r){       break;      }             $temp=$arr[$l];      $arr[$l]=$arr[$r];      $arr[$r]=$temp;      if($arr[$l]==$pivot){       --$r;      }      if($arr[$r]==$pivot){       ++$l;      }    }    if($l==$r){     $l++;     $r--;    }    if($left<$r) quickSort($left,$r,$arr);    if($right>$l) quickSort($l,$right,$arr); }    /**  * 快速排序方法 第二种实现方法 自己实现的  * PHP快速排序方法  * $order asc 小到大 desc大到小 默认是asc  * $order 的值只能为 asc desc 如果乱写一个值也是按asc排序的  */ function quickSort2($arr,$order = 'asc') {  if(count($arr) <= 1)   return $arr;     $arr_left = $arr_right = array();     $val = $arr[0];unset($arr[0]);     foreach ($arr as $v) {   if(strtolower($order) == 'desc'){    if($v < $val)     $arr_right[] = $v;    else     $arr_left[] = $v;   }else{    if($v > $val)     $arr_right[] = $v;    else     $arr_left[] = $v;   }  }     $arr_left = quickSort($arr_left,$order);  $arr_right = quickSort($arr_right,$order);     return array_merge($arr_left,array($val),$arr_right); }       //下面是查找 $arr=array(46,90,900,0,-1); //这是按顺序查询 function search(&$arr,$findVal){      $flag=false;   for($i=0;$i<count($arr);$i++){     if($findVal==$arr[$i]){       echo "找到了，下标为=$i";       $flag=true;       //查询一次，如果多次就不要这个 break;     }   }   if(!$flag){     echo "查无此数";   } }    //调用二分查找 $arr=array(0,90,900,99990);//注意，一定要是有序的 binarySwarch($arr,90,0,count($arr)-1);    //二分查找函数,它有一个前提，查找的数组必须是有序的 function binarySearch(&$arr,$findVal,$leftIndex,$rightIndex){   //如果$rightIndex < $leftIndex条件成立，说明没有这个数，则退出   if($rightIndex < $leftIndex){     echo "找不到该数";     return;   }   //首先找到中间这个数 round是出于如果出现小数，四舍五入   $middleIndex=round(($rightIndex+$leftIndex)/2);   //如果大于则向后面找   if($findVal > $arr[$middleIndex]){     binarySearch($arr,$findVal,$middleIndex+1,$rightIndex);     //如果小于中间数，则向前面找   }else if($findVal < $arr[$middleIndex]){     binarySearch($arr,$findVal,$leftIndex,$middleIndex-1);   }else{     echo "找到这个数。下标是$middleIndex";   } } ?>

查看更多关于PHP常用的排序和查找算法详解的详细内容...