<?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$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$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= 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){
$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$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";
}
}
?>