首页 / 网页编程 / PHP / PHP常用的排序和查找算法

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