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程序设计有所帮助。