php面试常见算法题

二分法查找：

/**
 *二分法查找
 * @param $array 是待查找的数组
 * @param $low 最小的键
 * @param $hight 最大的键
 * @param $k 要查找的位置
 */
function twofunction($array, $low, $height, $k)
{
    if (is_array($array)) {
        $mid = ($low + $height) / 2;
        if ($low <= $height) {
            if ($array[$mid] == $k) {
                return $mid;
            } elseif ($array[$mid] > $k) {
                return twofunction($array, $low, $mid - 1, $k);
            } elseif ($array[$mid] < $k) {
                return twofunction($array, $mid + 1, $height, $k);
            } else {
                return -1;
            }
        } else {
            return -1;
        }
    }
}

顺序查找

/**
 * 顺序查找
 * @param $arr是待查找的数组
 * @param @num是待查找数组中的元素个数
 * @param @val是待查找的元素
 * @return 元素位置
 */
function sort_function($arr, $num, $val)
{

    for ($i = 0; $i < $num; $i++) {
        if ($arr[$i] == $val) {
            break;
        }
    }
    if ($i < $num) {
        return $i;
    } else {
        return -1;
    }
}

二维数组排序

/**
  * @desc arraySort php二维数组排序 按照指定的key 对数组进行排序
  * @param array $arr 将要排序的数组
  * @param string $keys 指定排序的key
  * @param string $type 排序类型 asc | desc
  * @return array
 */
function arraySort($arr, $keys, $type)
{
    //先对指定的下标元素进行排序
    $keysvalue = $new_array = array();
    foreach ($arr as $k => $v) {
        $keysvalue[$k] = $v[$keys];
    }
    $type == 'asc' ? asort($keysvalue) : arsort($keysvalue);
    //数组指针指向第一个
    reset($keysvalue);
    //将下标添加上去
    foreach ($keysvalue as $k => $v) {
        $new_array[$k] = $arr[$k];
    }
    return $new_array;
}

冒泡排序

/*冒泡排序
在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，
让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换
*/
function maopao($array)
{
	$len = count($array);
    if ($len <= 1) return $array;
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $tem = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $tem;
            }
        }
    }
    return $array;
}

快速排序

/*快速排序
选择一个基准元素，通常选择第一个元素或者最后一个元素。
通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，
然后再用同样的方法递归地排序划分的两部分。

*/
function quick_sort($array)
{
	$len = count($array);
    if ($len <= 1) return $array;
    $key = $array[0];
    $array_left = array();
    $array_right = array();
    for ($i = 1; $i < $len; $i++) {
        if ($key > $array[$i]) {
            array_push($array_left, $array[$i]);
        } else {
            $array_right[] = $array[$i];
        }
    }
    $array_left = quick_sort($array_left);
    $array_right = quick_sort($array_right);

    return array_merge($array_left, array($key), $array_right);
}

选择排序

/*选择排序
在要排序的一组数中，选出最小的一个数与第一个位置的数交换。
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
*/
function select_sort($array)
{
    if (count($array) <= 1) return $array;
    //双重循环完成，外层控制轮数，内层控制比较次数
    for ($i = 0; $i < count($array) - 1; $i++) {
        //先假设最小的值的位置
        $min = $i;
        for ($j = $i + 1; $j < count($array); $j++) {
            if ($array[$min] > $array[$j]) {
                $min = $j; //选出最小的值
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可。
        if ($min != $i) {
            $tmp = $array[$min];
            $array[$min] = $array[$i];
            $array[$i] = $tmp;
        }
    }
    return $array;
}

插入排序

/*插入排序，不推荐使用
 在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第 n 个数插到前面的有序数中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。
 */
function insert_sort($array)
{ //小到大排序
    if (count($array) <= 1) return $array;
    for ($i = 1; $i < count($array); $i++) {
        $tmp = $array[$i];
        //内层循环控制，比较并插入
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($array[$j] > $tmp) {
                //发现插入的元素要大，交换位置，将后边的元素与前面的元素互换
                $array[$j + 1] = $array[$j];
                $array[$j] = $tmp;
            } else {
                break;
            }
        }
    }
    return $array;
}