1.顺序查找
思路分析: 从数组的第一个元素开始一个一个向下查找,如果有和目标一致的元素,查找成功;如果到最后一个元素仍没有目标元素,则查找失败。
代码实现:
<?php
function search($arr,$k){
$n = count($arr);
$arr[$n]= $k;
for($i=0; $i<$n; $i++){
if($arr[$i]==$k){
break;
}
}
if ($i<$n){
return $i;
}else{
return -1;
}
}
2.二分查找
思路分析:先取数组中间的值floor((low+top)/2), 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作;若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ,重复第二步操作直至找出目标数字。
代码实现:
// 非递归
// $target是要查找的目标 $arr是已经排序好的数组
function binary(&$arr,$low,$top,$target){
while($low <= $top){
//由于php取商是有小数的,所以向下取整,不过也可不加,数组也会取整
$mid = floor(($low+$top)/2);
echo $mid."<br>";
if($arr[$mid]==$target){
return $arr[$mid];
}elseif($arr[$mid]<$target){
$low = $mid+1;
}else{
$top = $mid-1;
}
}
return -1;
}
// 递归
function binaryRecursive($arr,$low,$top,$target){
if($low<=$top){
$mid = floor(($low+$top)/2);
if($arr[$mid]==$target){
return $arr[$mid];
}elseif($arr[$mid]<$target){
return binaryRecursive($arr,$mid+1,$top,$target);
}else{
return binaryRecursive($arr,$low,$top-1,$target);
}
}else{
return -1;
}
}
3.写一个二维数组排序算法函数,可以调用php内置函数,能够具有通用性。
代码实现:
function array_sort($arr, $keys, $order=0) {
if (!is_array($arr)) {
return false;
}
$keysvalue = array();
foreach($arr as $key => $val) {
$keysvalue[$key] = $val[$keys];
}
if($order == 0){
asort($keysvalue);
}else {
arsort($keysvalue);
}
reset($keysvalue);
foreach($keysvalue as $key => $vals) {
$keysort[$key] = $key;
}
$new_array = array();
foreach($keysort as $key => $val) {
$new_array[$key] = $arr[$val];
}
return $new_array;
}
4.写一个函数,能够遍历一个文件下的所有文件和子文件夹
代码实现:
<?php
function my_scandir($dir){
$files = array();
if($handle = opendir($dir)) {
while (($file = readdir($handle))!== false) {
if($file != '..' && $file != '.') {
if(is_dir($dir."/".$file)){
$files[$file]=my_scandir($dir."/".$file);
}else{
$files[] = $file;
}
}
} closedir($handle);
return $files;
}
}
5.归并排序
代码实现:
function Merge(&$arr, $left, $mid, $right) {
$i = $left;
$j = $mid + 1;
$k = 0;
$temp = array();
while ($i <= $mid && $j <= $right)
{
if ($arr[$i] <= $arr[$j])
$temp[$k++] = $arr[$i++];
else
$temp[$k++] = $arr[$j++];
}
while ($i <= $mid)
$temp[$k++] = $arr[$i++];
while ($j <= $right)
$temp[$k++] = $arr[$j++];
for ($i = $left, $j = 0; $i <= $right; $i++, $j++)
$arr[$i] = $temp[$j];
}function MergeSort(&$arr, $left, $right)
{
if ($left < $right)
{
$mid = floor(($left + $right) / 2);
MergeSort($arr, $left, $mid);
MergeSort($arr, $mid + 1, $right);
Merge($arr, $left, $mid, $right);
}
}
还有部分其他类型的算法面试题参考:
1.http://blog.csdn.net/caleng/article/details/5276403
2.http://www.cnblogs.com/jackluo/p/3139770.html
部分摘自网络 ,待验证。