<?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";
 }
}
?>