二分法和快速排序的PHP实现

sxyzy

//二分法
function binarySearch($a, $val){
$low = 0;
$high= count($a) - 1;
while($low <= $high){
$mid = intval(($low+$high)/2);
if($a[$mid] == $val) return $mid;
if($a[$mid] > $val){
$high = $mid - 1;
}else{
$low = $mid + 1;
}
}
return -1;
}

//快速排序算法
function quickSort(&$a, $l, $r){
if($l >= $r) return;
$m = pation($a, $l, $r);
quickSort($a, $l, $m-1);
quickSort($a, $m+1, $r);
}

function pation(&$a, $l, $r){
$pivot = $a[$l];
$i = $l + 1;
$j = $r;
while(1){
while($a[$i] > $pivot && $i < $j) $i++;
while($a[$j] < $pivot) $j--;
if($i>=$j) break;
$temp = $a[$i];
$a[$i]= $a[$j];
$a[$j]= $temp;
}
$a[$l] = $a[$j];
$a[$j] = $pivot;
return $j;
}