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

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

冒泡排序算法

将下面各数进行从大到小的顺序进行排列（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));

运行实例 »

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