Commonly used sorting and search algorithms in PHP, php sorting algorithm_PHP tutorial

Commonly used sorting and search algorithms in PHP, PHP sorting algorithm

This article summarizes common PHP sorting algorithms and searches, which has good reference value when designing algorithms. Now share it with everyone for reference. The details are as follows:

<&#63;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";
  }
}
&#63;>

I hope the sorting algorithm and search algorithm examples described in this article will be helpful to everyone’s PHP programming.

http://www.bkjia.com/PHPjc/1044259.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/1044259.htmlTechArticlePHP commonly used sorting and search algorithms, php sorting algorithm This article summarizes common php sorting algorithms and searches, in progress It has good reference value when designing algorithms. Now share it with everyone for reference...