PHP面試題之算法解析

面試中經常被問到會什麼算法,這裡整合一些常見的算法及它們的實現原理.下面的例子都是經過測試可用的,如果有什麼問題請告知!!

本人小白,如果有更好的實現方式,敬請賜教,感激不盡!!!!

冒泡排序,快速排序,選擇排序,二分法查找,快速查找

/** 
* 冒泡排序
* 相鄰2數比較,小的在前,大的在後
* 數組有幾個元素,就要比較幾輪 $i
* 每輪需要比較的次數為,數組元素個數-已比較的次數 $j
* @param   array  $array 要操作的數組
* @return  array  $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;
}
}