PHP面试相关算法

一、冒泡排序

基本思想:
对需要排序的数组从后往前(逆序)进行多遍的扫描,当发现相邻的两个数值的次序与排序要求的规则不一致时,就将这两个数值进行交换。这样比较小(大)的数值就将逐渐从后面向前面移动。
//冒泡排序:
在这里解释下内部循环为何减去$i(每次大循环都将最大的数放到新数组前面或后面,所以既然最大的数已经排出来当再次执行内部循环时就不用考虑最大的那个数所以要减去$i。)

<?php
function mysort($arr)
{
for($i = 0; $i < count($arr)-1; $i++)
{
$isSort = false;
for ($j=0; $j< count($arr) – $i – 1; $j++)//减1是因为下面会判断arr[$j+1],防止下标越界.
{
if($arr[$j] < $arr[$j+1])
{
$isSort = true;
$temp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $temp ;
}
}
if($isSort)
if(!$isSort)
break;
}
return $arr;
}
$arr = array(3,1,2);
var_dump(mysort($arr));
?>
二、快速排序
在数组中挑出一个元素(多为第一个)作为标尺,扫描一遍数组将比标尺小的元素排在标尺之前,将所有比标尺大的元素排在标尺之后,通过递归将各子序列分别划分为更小的序列直到所有的序列顺序一致。

<?php

//快排
function quicksort(&$arr,$left,$right){
if(count($arr)<=1)return $arr;
if($left>$right)return;
$i = $left;
$j = $right;
//这里做下标记
$guard = $arr[$left];
while($i<$j){
//以左边第一个元素作为标尺,一定要先从右边移动哨兵$j
while($i<$j && $arr[$j]>=$guard)$j–;
while($i<$j && $arr[$i]<=$guard)$i++;
//$j指向遇到比标尺大的值
//$i指向到比自己小的值
//进行位置交换
if($i<$j)list($arr[$j],$arr[$i]) = swap($arr[$j],$arr[$i]);
var_dump(“交换$arr[$j]和$arr[$i]”);
//促使标尺左边都是比自己小的,标尺右边都是比自己大的
}
//参考标记处:实际上就是将$i和$j两个哨兵相遇时对应的值
//与标尺对应的值做下交换
$arr[$left] = $arr[$i];
$arr[$i] = $guard;
quicksort($arr,0,$i-1);
quicksort($arr,$i+1,$right);
}

function swap($A,$B){
$temp = $A;
$A = $B;
$B = $temp;
return array($A,$B);
}
$arr = array(2,1,3,2,5,4,9,6,7);
quicksort($arr,0,count($arr)-1);
var_dump($arr);

三、二分查找
假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。(数据量大的时候使用)

<?php
//二分查找
function bin_search($arr,$low,$high,$k)
if($low <= $high)
$mid = intval(($low + $high)/2);
if($arr[$mid] == $k)
return $mid;
else if($k < $arr[$mid])
return bin_search($arr,$low,$mid-1,$k);
else
return bin_search($arr,$mid+1,$high,$k);
return -1;
$arr = array(1,2,3,4,5,6,7,8,9,10);
print(bin_search($arr,0,9,3));
四、顺序查找
从数组的第一个元素开始一个一个向下查找,如果有和目标一致的元素,查找成功;如果到最后一个元素仍没有目标元素,则查找失败。
//顺序查找
function seq_search($arr,$n,$k)
$array[$n] = $k;
for($i = 0;$i < $n; $i++)
if($arr[$i] == $k)
if($i < $n)
return $i;
else
return -1;
五、写一个函数,能够遍历一个文件下的所有文件和子文件夹
<?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;
var_dump(my_scandir(‘../’));
六、写一个函数,尽可能高效的从一个标准url中取出文件的扩展名
function getExt($url)
$arr = parse_url($url);//parse_url解析一个 URL 并返回一个关联数组,包含在 URL 中出现的各种组成部分
//’scheme’ => string ‘http’ (length=4)
//’host’ => string ‘www.sina.com.cn’ (length=15)
//’path’ => string ‘/abc/de/fg.php’ (length=14)
//’query’ => string ‘id=1’ (length=4)
$file = basename($arr[‘path’]);// basename函数返回路径中的文件名部分
$ext = explode(‘.’, $file);
return $ext[count($ext)-1];
print(getExt(‘http://www.sina.com.cn/abc/de/fg.html.php?id=1’));
七、实现中文字符串截取无乱码的方法
可使用mb_substr,但是需要确保在php.ini中加载了php_mbstring.dll,即确保“extension=php_mbstring.dll”这一行存在并且没有被注释掉,否则会出现未定义函 数的问题。

发表评论