<?php
/**
 * PHP最常用的四個排序方法及二種查找方法
 * 下面的排序方法全部都通過測試
 * auther : soulence
 * date : 2015/06/20
 */
 
//PHP冒泡排序法
function bubbleSort(&$arr){
 //這是一個中間變量
 $temp=0;
 //我們要把數(shù)組，從小到大排序
 //外層循環(huán)
 $flag=false;//這個優(yōu)化之后效率會很高，一般夠用
 for($i=0;$i<count($arr)-1;$i++){
  
   for($j=0;$j<count($arr)-1-$i;$j++){
     //說明前面的數(shù)比后面的數(shù)大，就要交換
     if($arr[$j]>$arr[$j+1]){
        $temp=$arr[$j];
        $arr[$j]=$arr[$j+1];
        $arr[$j+1]=$temp;
        $flag=true;
     }
   }
   if(!$flag){
    //已經(jīng)是有序了
    break;
   }
   $flag=false;
  }
}
 
//PHP選擇排序法  效率比冒泡要高
function selectSort(&$arr){
  $temp=0;
  for($i=0;$i<count($arr)-1;$i++){
    //假設(shè)$i就是最小的數(shù)
    $minVal=$arr[$i];
    //記錄我認(rèn)為的最小數(shù)的下標(biāo)
    $minIndex=$i;
    for($j=$i+1;$j<count($arr);$j++){
      //說明我們認(rèn)為的最小值，不是最小
      if($minVal>$arr[$j]){
         $minVal=$arr[$j];
         $minIndex=$j;
      }
    }
    //最后交換
    $temp=$arr[$i];
    $arr[$i]=$arr[$minIndex];
    $arr[$minIndex]=$temp;
  }
}
 
//插入排序法(小到大排序)  效率又比 選擇排序法要高一些
function insertSort(&$arr){
  //先默認(rèn)下標(biāo)為0的這個數(shù)已經(jīng)是有序
  for($i=1;$i<count($arr);$i++){
    //$insertVal是準(zhǔn)備插入的數(shù)
    $insertVal=$arr[$i];
    //準(zhǔn)備先和誰下標(biāo)為$inserIndex的比較
    $inserIndex=$i-1;
    //如果這個條件滿足，說明我們還沒有找到適當(dāng)?shù)奈恢?
    while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){
    //同時把數(shù)后移
      $arr[$inserIndex+1] = $arr[$inserIndex];
      $inserIndex--;
    }
    //插入（這時就給$inserIndex找到適當(dāng)?shù)奈恢茫?
    $arr[$inserIndex+1] = $insertVal;
  }
}
 
  
//快速排序法 第一種寫法 不是我實現(xiàn)的
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);
}
 
/**
 * 快速排序方法 第二種實現(xiàn)方法 自己實現(xiàn)的
 * PHP快速排序方法
 * $order asc 小到大 desc大到小 默認(rèn)是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 "找到了，下標(biāo)為=$i";
      $flag=true;
      //查詢一次，如果多次就不要這個 break;
    }
  }
  if(!$flag){
    echo "查無此數(shù)";
  }
}
 
//調(diào)用二分查找
$arr=array(0,90,900,99990);//注意，一定要是有序的
binarySwarch($arr,90,0,count($arr)-1);
 
//二分查找函數(shù),它有一個前提，查找的數(shù)組必須是有序的
function binarySearch(&$arr,$findVal,$leftIndex,$rightIndex){
  //如果$rightIndex < $leftIndex條件成立，說明沒有這個數(shù)，則退出
  if($rightIndex < $leftIndex){
    echo "找不到該數(shù)";
    return;
  }
  //首先找到中間這個數(shù) round是出于如果出現(xiàn)小數(shù)，四舍五入
  $middleIndex=round(($rightIndex+$leftIndex)/2);
  //如果大于則向后面找
  if($findVal > $arr[$middleIndex]){
    binarySearch($arr,$findVal,$middleIndex+1,$rightIndex);
    //如果小于中間數(shù)，則向前面找
  }else if($findVal < $arr[$middleIndex]){
    binarySearch($arr,$findVal,$leftIndex,$middleIndex-1);
  }else{
    echo "找到這個數(shù)。下標(biāo)是$middleIndex";
  }
}
?>