最近在看PHP的时候温习了一下原来学过的排序算法（忘的都差不多了-_-），故在此记录一下

斐波拉契数列

//打印数列
$arr = array(1 => 1,2 => 1);
echo "<pre>";
for ($i = count($arr); $i < 15; $i++){
    $arr[$i + 1] = $arr[$i] + $arr[$i - 1];
}
print_r($arr);//打印数列前15位
//下面计算数列的第几位
function a($n){
    if($n ==1 || $n == 2) return 1;

    return a($n - 1) + a($n -2);
}
echo a(15);//打印数列第15位

排序算法

冒泡排序

$arr = array(5,7,3,9,1,6,2,8,4);
$len = count($arr);
for ($i = 0; $i < $len; $i++){
    for ($j = 0; $j < $len - $i -1;$j++){
        if($arr[$j] > $arr[$j+1]){
            $temp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $temp;
        }
    }
}
echo "<pre>";
print_r($arr);

选择排序

$arr = array(5,7,3,9,1,6,2,8,4);
$len = count($arr);
for ($i = 0;$i <$len ;$i++){
    $min = $i;
    for ($j = $i + 1;$j < $len;$j++){ //这个for循环选出最小值
        if($arr[$j]< $arr[$min]){
            $min = $j;
        }
    }
    if($min != $i){  //选择最小值放前面
        $temp = $arr[$i];
        $arr[$i] = $arr[$min];
        $arr[$min] = $temp;
    }
}
echo "<pre>";
print_r($arr);

插入排序

$arr = array(5,7,3,9,1,6,2,8,4);
$len = count($arr);
for($i = 1;$i < $len;$i++){
    $temp = $arr[$i];    //从第二个数据开始依次取出数据与前面已经排好的进行比较
    $flag = false;
    for($j = $i - 1; $j >= 0;$j--){
        if($arr[$j] > $temp){
            $arr[$j + 1] = $arr[$j];
            //$arr[$j] = $temp;     //优化后略过了这一次赋值，意思就是temp元素依旧存在，没进入数组，当前面的元素都交换完成后，才在后面的if语句中进行最后的赋值操作
            $flag = true;
        }else{
        break;   //这里的作用是如果在判断的时候取出来的就已经比他左边的要大了，就不用进行交换了，直接break
        }
    }
    if($flag){  //如果交换了，则进行temp赋值
        $arr[$j + 1] = $temp; //这里$j需要加一的原因是在上面的循环最后执行了一次$j--的操作，于是这里需要把1加上
    }
}
echo "<pre>";
print_r($arr);

快速排序

$arr = array(5,7,3,9,1,6,2,8,4);
function quick_sort($arr){
    $len = count($arr);
    if($len <= 1) return $arr;

    $left = $right = array();
    for($i = 1;$i < $len;$i++){
        if($arr[0] > $arr[$i]){
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }

    $left = quick_sort($left);//递归
    $right = quick_sort($right);//递归

    return array_merge($left,(array)$arr[0],$right);//合并数组，注意这里元素必须全是数组才能进行操作，$arr[0]为元素，所以需要强制转换成数组，或者用array($arr[0])也可以
}
echo "<pre>";
print_r(quick_sort($arr));

归并排序

$arr = array(5,7,3,9,1,6,2,8,4);
function merge_sort($arr){
    $len = count($arr);
    if($len <= 1) return $arr;
    $a  = floor($len / 2);//舍去法取整
    $left = array_slice($arr,0,$a);//array_slice从数组中取出一段序列
    $right = array_slice($arr,$a);
    $left = merge_sort($left);//递归
    $right = merge_sort($right);//递归
    $m = array();
    while(count($left) && count($right)) {//当有一边为0则结束返回
        $m[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    return array_merge($m,$left,$right);//后两个数组的放置对结果没影响
}
echo "<pre>";
print_r(merge_sort($arr));

查找算法

这里有一种数组遍历查找就没写了

二分法查找

注：二分法查找前要求数列是已经排好序了的

$arr = array(1,2,3,4,5,6,7,8,9);
function check($arr,$num){
    $left = 0;
    $right = count($arr);
    while($left <= $right){
        $middle = floor(($left + $right) / 2);
        if($arr[$middle] == $num){
            return $arr[$middle];
        }
        if($arr[$middle] > $num){
            $right = $middle - 1;
        }else{
            $left = $middle + 1;
        }
    }
    return false;
}
print_r(check($arr,11));

这个方法在查找的时候如果要查的数据不在数组里就会报下面的注意事项（在的话不会报错），返回的结果false还是有的

Notice:  Undefined offset: 9 in C:\xxx\test.php on line 7
Notice:  Undefined offset: 9 in C:\xxx\test.php on line 10

原因还没找到，如果有大佬知道的话欢迎留言指出，wtcl -_-，没有的话坑先留着后面再填

二分归并法查找

$arr = array(1,2,3,4,5,6,7,8,9);
function check($arr,$num){
    $len = count($arr);
    $a = floor($len / 2);
    $left = array_slice($arr,0,$a);
    $right = array_slice($arr,$a);
    
    while(count($left) && count($right)){
        if($arr[$a] === $num ){
            return $arr[$a];
        }else if($arr[$a] > $num){
            return check($left,$num);
        }else{
            return check($right,$num);
        }
    }
    return false;
}
print_r(check($arr,8));

web:dog: