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