博主信息
Whitney的博客
博文
41
粉丝
3
评论
2
访问量
40514
积分:0
P豆:127

面试过程中经常涉及的一些算法

2020年03月14日 18:13:07阅读数:164博客 / Whitney的博客 / PHP

面试过程中经常涉及的一些算法

冒泡排序算法

将下面各数进行从大到小的顺序进行排列(23,4,56,6,8,9)

实例

function bubbleSort($arr) {
for ($i = 0; $i < count($arr);$i++ ) {
	for ($j = 0; $j < count($arr)-1;$j++) {
	      if($arr[$j]>$arr[$j+1]) {
		   $temp = $arr[$j];
		   $arr[$j] = $arr[$j+1];
		   $arr[$j+1] = $temp;
	}
}
}
	return $arr;
}

$arr = array(23,4,56,6,8,9);
print_r(bubbleSort($arr));

运行实例 »

点击 "运行实例" 按钮查看在线实例

快速排序算法

思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后仔按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列;

实例

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);
}

$arr = array(23,4,56,6,8,9);
print_r(quickSort($arr));

运行实例 »

点击 "运行实例" 按钮查看在线实例

二分查找算法

思想:(1)确定该区间的中间位置K;(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找;       时间复杂度:O(log2n)

实例

function binsearch($x,$a){
    $c=count($a);
    $lower=0;
    $high=$c-1;
    while($lower<=$high){
        $middle=intval(($lower+$high)/2);
        if($a[$middle]>$x){
            $high=$middle-1;
        } elseif($a[$middle]<$x){
            $lower=$middle+1;
        } else{
            return $middle;
        }
    }
    return -1;
}

$arr = array(23,4,56,6,8,9);
var_dump(binsearch(4,$arr));

运行实例 »

点击 "运行实例" 按钮查看在线实例

全部评论

文明上网理性发言,请遵守新闻评论服务协议

条评论
暂无评论暂无评论!