查找&&排序 （数组）

<?php

//二分查找法
function binSearch($arr, $search)
{
    $height = count($arr) - 1;
    $low = 0;
    while ($low <= $height) {
        $mid = floor(($low + $height) / 2);
        //获取中间数
        if ($arr[$mid] == $search) {
            return $mid; //返回
        } elseif ($arr[$mid] < $search) {
            //当中间值小于所查值时，则$mid左边的值都小于$search，此时要将$mid赋值给$low
            $low = $mid + 1;
        } elseif ($arr[$mid] > $search) {
            //中间值大于所查值,则$mid右边的所有值都大于$search,此时要将$mid赋值给$height
            $height = $mid - 1;
        }
    }

    return '查找失败';
}

//二分查找递归实现
function binSearch2($arr, $low, $height, $k)
{
    if ($low <= $height) {
        $mid = floor(($low + $height) / 2); //获取中间数
        if ($arr[$mid] == $k) {
            return $mid;
        } elseif ($arr[$mid] < $k) {
            return binSearch2($arr, $mid + 1, $height, $k);
        } elseif ($arr[$mid] > $k) {
            return binSearch2($arr, $low, $mid - 1, $k);
        }
    }

    return '查找失败';
}

//顺序查找
function seqSearch($arr, $k)
{
    foreach ($arr as $key => $val) {
        if ($val == $k) {
            return $key;
        }
    }

    return -1;
}

$arr = array(1, 2, 3, 4);
echo binSearch($arr, 4).'<br/>';
echo binSearch2($arr, 0, 4, 4).'<br/>';
echo seqSearch($arr, 4).'<br/>';
echo in_array(4, $arr).'<br/>';
echo array_search(4, $arr);

<?php

/**
 * 冒泡排序
 * 思想：将数组中前后两个相邻的数值进行比较条件成立则交换.
 * 缺点：替换次数多，效率低.
 */
function bubbleSort($arr)
{
    // 第一层for循环可以理解为从数组中键为0开始循环到最后一个
    for ($i = 0; $i < count($arr); ++$i) {
        // 第二层将从键为$i的地方循环到数组最后
        for ($j = $i + 1; $j < count($arr); ++$j) {
            // 比较数组中相邻两个值的大小
            if ($arr[$i] > $arr[$j]) {
                $tmp = $arr[$i]; // 这里的tmp是临时变量
            $arr[$i] = $arr[$j]; // 第一次更换位置
            $arr[$j] = $tmp;            // 完成位置互换
            }
        }
    }

    return $arr;
}

/**
 * 选择排序
 * 思想：假设第一个是最小的 ，循环与数组中第一个比较 ，如果比其还小 ， 则记录下标 进行数值交换
 * 缺点：效率相比冒泡高.
 */
function selectionSort($array)
{
    for ($i = 0; $i < count($array) - 1; ++$i) {
        /*findtheminest*/
        $min = $i;

        for ($j = $i + 1; $j < count($array); ++$j) {
            //由小到大排列
            if ($array[$min] > $array[$j]) {
                //表明当前最小的还比当前的元素大
                $min = $j;
                //赋值新的最小的
            }
        }
        /*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
        if ($min != $i) {
            $temp = $array[$min];
            $array[$min] = $array[$i];
            $array[$i] = $temp;
        }
    }

    return $array;
}

/**
 * 插入排序
 * 思想：将插入的数据保存在变量中，与数组中的每个数比较 找到合适的位置 进行插入
 * 缺点： 效率相对来说比较高.
 */
function insertSort($arr)
{
    for ($i = 0; $i < count($arr); ++$i) {
        //当前要插入的值与下标
        $insertVal = $arr[$i];
        $insertIndex = $i - 1;
        //判断当前的值是否大于0并且大于它要插入的数
        while ($insertIndex >= 0 && $insertVal < $arr[$insertIndex]) {
            $arr[$insertIndex + 1] = $arr[$insertIndex];
            --$insertIndex;
        }
        $arr[$insertIndex + 1] = $insertVal;
    }

    return $arr;
}

/**
 * 快速排序
 * 思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列.
 * 效率很高.
 */
function quickSort($arr)
{
    if (count($arr) <= 1) {
        return $arr;
    }

    $key = $arr[0]; // 第一个元素
    $left_arr = array(); // 左边数组
    $right_arr = array(); // 右边数组

    for ($i = 1; $i < count($arr); ++$i) {//从第2个元素开始遍历
        if ($arr[$i] <= $key) {//小于第一个元素的，放在左边数组
            $left_arr[] = $arr[$i];
        } else {
            $right_arr[] = $arr[$i];
        } //大于第一个元素的，放在右边
    }

    $left_arr = quickSort($left_arr); //对左边的数组排序
    $right_arr = quickSort($right_arr); //对右边的数组排序

    return array_merge($left_arr, array($key), $right_arr); //合并数组
}

$arr = array(13, 89, 23, 9, 19, 88, 56, 78, 34, 69, 10, 14);

var_dump(insertSort($arr));