PHP面试题之算法解析

面试中经常被问到会什么算法,这里整合一些常见的算法及它们的实现原理.下面的例子都是经过测试可用的,如果有什么问题请告知！！本人小白,如果有更好的实现方式,敬请赐教,感激不尽！！！！冒泡排序,快速排序,选择排序,二分法查找,快速查找/** * 冒泡排序* 相邻2数比较,小的在前,大的在后* 数组有几个元素,就要比较几轮 $i* 每轮需要比较的次数为,数组元素个数-已比较的次数 $j* @param array$array 要操作的数组* @returnarray$array 返回的数组*/function bubbleSort（$array）{$cnt = count（$array）;for（$i = 0; $i < $cnt ; $i++）{for（$j = 0 ; $j < （$cnt-$i-1） ; $j++）{if（$array[$j] > $array[$j+1]）{$temp = $array[$j];$array[$j] = $array[$j+1];$array[$j+1] = $temp;}}}return $array;}
/*** 快速排序* 递归实现* 获取数组第一个数,循环使后面的数与其比较,* 比其小的放在一个数组中,比其大的放在一个数组中* 将2个数组递归调用,直到最终数组元素小于等于1时,没有可以比较的元素* 通过array_merge函数,将比较的数组按大小顺序合并然后一层一层的return出去,最终实现从小到大排序* @param array $array 要操作的数组* @return array $array 返回的数组*/function quickSort（$array）{if（count（$array） <= 1 ） return $array;$key = $array[0];$left_arr = array（）;$right_arr = array（）;for （$i=1;$i<count（$array）;$i++）{if（$array[$i] <= $key）{$left_arr[] = $array[$i];}else{$right_arr[] = $array[$i];}}$left_arr = quickSort（$left_arr）;$right_arr = quickSort（$right_arr）;return array_merge（$left_arr,array（$key）,$right_arr）;} /**
* 选择排序
* 2层循环
* 第一层逐个获取数组的值 $array[$i]
* 第二次遍历整个数组与$array[$i]比较（$j=$i+1已经比较的,不再比较,减少比较次数）
* 如果比$array[$i]小,就交换位置
* 这样一轮下来就可以得到数组中最小值
* 以此内推整个外层循环下来就数组从小到大排序了
* @param array $array 要比较的数组
* @return array $array 从小到大排序后的数组
*/

function selectSort（$array）{
$cnt = count（$array）;
for（$i=0;$i<$cnt;$i++）{
for（$j=（$i+1）;$j<$cnt;$j++）{
if（$array[$i]>$array[$j]）{
$tmp = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $tmp;
}
}
}
return $array;
} /**
* 二分法查找一个值在数组中的位置
* @param array $array 操作的数组
* @param void $val 要查找的值
* @return int $mid 返回要查找的值在数组中的索引,如果不存在返回-1
*/

function binarySearch（$array,$val）
{
$cnt = count（$array）;
$low = 0;
$high = $cnt - 1;
while （$low <= $high）{
$mid = intval（（$low + $high）/2）;
if（$array[$mid] == $val）{
return $mid;
}

if（$array[$mid] < $val）{
$low = $mid + 1;
}

if（$array[$mid] > $val）{
$high = $mid - 1;
}
}

return -1;
} /**
* 顺序查找（最简单,效率低下）
* 通过循环数组查找要的值
* @param array $array 要操作的数组
* @param void $val 要查找的值
* @return int 如果存在,返回该值在数组中的索引,否则返回-1
*/

function seqSch（$array,$val）
{
for（$i=0;$i<count（$array）;$i++）{
if（$array[$i] == $val）
break;
}

if（$i < count（$array））{
return $i;
}else{
return -1;
}
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-10/124070.htm