PHP-算法初识~

//递推思想(算法)
//需求:规律1 1 2 3 5 ...
//求出指定位数对应的值
//已知条件:第一个和第二个数都为1,第三个开始为前两个之和


function my_recursive($des){
    //判断:如果为第一个或第二个直接返回结果
    if($des==1||$des==2) return 1;

    //开始计算:
    $f[1] =1;
    $f[2]=1;  //如果想要第一个或者第二个结果,那么可以直接给出

    for($i=3;$i<=$des;$i++){
        $f[$i]=$f[$i-1]+$f[$i-2];
    }
    //返回结果
    return $f[$des];
}

//调用函数并查看结果
echo my_recursive(10);

结果:55

//递归思想
//递归一定有函数

function recursion($n){
    //递归出口
    if($n == 1 || $n == 2 ) return 1;
    //递归点:求N的值,与求N-1的值一模一样,只是N-1的规模比N小
    return recursion($n-1)+recursion($n-2);
}

echo recursion(3);

//数组排序算法:冒泡排序

$arr = array(1,4,2,9,7,5,8);
//2.想办法让下面可以每次最大值的代码重复执行
for($i=0,$len = count($arr);$i<$len;$i++){
    //1. 想办法将最大的值放大最右边
    for($j = 0; $j < $len - 1-$i;$j++){
        //判断:两两相比
        if($arr[$j]>$arr[$j+1]){
            //左边比右边大:交换
            $temp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $temp;
        }
    }
}
echo '<pre>';
print_r($arr);

结果:
Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 5
    [4] => 7
    [5] => 8
    [6] => 9
)

//数组排序算法:选择排序
$arr = array(1,5,2,9,6,3,4);

//1.确定要交换多少次:一次只能找一个最小的,需要找数组长度对应的次数
for($i=0,$len=count($arr);$i<$len;$i++){
    //2.假设当前第一个已经排好序
    $min = $i; //当前第一个数是最小的
    //3.拿当前最小的去比较剩余的其他数
    for($j=$i+1;$j<$len;$j++){
        //4.比较:比较当前元素与选定的最小的元素
        if($arr[$j]<$arr[$min]){
            //说明当前的$min不合适
            $min = $j;
        }
    }
    //5.交换当前选定的值与实际最小的元素值
    if($min != $i){
        $temp = $arr[$i];
        $arr[$i]=$arr[$min];
        $arr[$min]=$temp;
    }
}
echo '<pre>';
print_r($arr);

结果:
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 9
)

//数组排序算法:插入排序

$arr = array(4,2,6,8,9,5);
//1、确定要插入多少回(假设一个数组一次性插入到对的位置,同时第一个位置是假设对的)
for($i = 1,$len = count($arr);$i< $len;$i++){
    //2、取出当前要插入的元素的值
    $temp = $arr[$i];
    //3、让该数据与前面已经排好序的数组元素重复比较(挨个比较),直到的位置(交换)
    for($j =$i - 1;$j >= 0;$j--){
        // 4、比较
        if($arr[$j] >$temp){
            //说明当前要插入的元素,比前面的已经排好序的元素的值要小:交换位置
            $arr[$j+1] = $arr[$j];
            $arr[$j] = $temp;
        }else{
        //说明当前待插入元素,比前面的元素要大:说明位置正确
        break;
        }
    }
}
echo '<pre>';
print_r($arr);

结果:
Array
(
    [0] => 2
    [1] => 4
    [2] => 5
    [3] => 6
    [4] => 8
    [5] => 9
)

//PHP数组排序:快速排序
$arr = array(5,6,3,4,9,2,7,8);
//快速排序
function quick_sort($arr){
    //递归出口
    $len = count($arr);
    if($len <= 1) return $arr;
    //取出某个元素,然后将剩余的数组元素,分散到两个不同的数组中
    $left = $right =array();
    for($i=1;$i<$len;$i++){
        //第一个元素作为比较元素
        //比较:小的放left中,大的放right中
        if($arr[$i]<$arr[0]){
            $left[]=$arr[$i];
        }else{
            $right[]=$arr[$i];
        }
    }
    //$left和$right数组没有排序好:递归点
    $left = quick_sort($left);
    $right = quick_sort($right);
    //合并三个"数"组
    return array_merge($left,(array)$arr[0],$right);
}

print_r(quick_sort($arr));
结果:
Array
(
    [0] => 2
    [1] => 3
    [2] => 4
    [3] => 5
    [4] => 6
    [5] => 7
    [6] => 8
    [7] => 9
)

二路归并实现:
$arr1 = array(1,3,5);
$arr2 = array(2,4,6);

//取出一个空数组用于归并空间
$arr3 = array();
while(count($arr1)&&count($arr2)){
    //只要$arr1和$arr2里面还有元素,就进行循环
    //取出每个元组的第一个元素:进行比较
    $arr3[] = $arr1[0]<$arr2[0]?array_shift($arr1):array_shift($arr2);
}
//合并结果
print_r(array_merge($arr3,$arr1,$arr2));
结果:
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
)

$arr=array(4,7,2,1,5,9,3);
//归并排序函数
function merge_sort($arr){
    //递归出口
    $len = count($arr);
    if($len<=1) return $arr;
    //拆分
    $middle = floor($len/2);
    $left = array_slice($arr,0,$middle);
    $right = array_slice($arr,$middle);
    //递归点:$left和$right都没有排好序:而且可能是多个元素的数组
    $left = merge_sort($left);
    $right = merge_sort($right);
    //假设:左边和右边都已经排好序了
    $m = array();
    while(count($left)&&count($right)){
        //只要$arr1和$arr2里面还有元素,就进行循环
        //取出每个元组的第一个元素:进行比较
        $m[] = $left[0]<$right[0]?array_shift($left):array_shift($right);
    }
    //返回结果
    return array_merge($m,$left,$right);
}
print_r(merge_sort($arr));

结果:
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 7
    [6] => 9
)

//顺序查找
$arr = array(1,3,6,8,23,68,100);
//顺序查找:v哦那个数组第一个元素快速,挨个匹配
function check_order($arr,$num){
    //全部匹配
    for($i=0,$len=count($arr);$i<$len;$i++){
        //判断
        if($arr[$i] == $num){
            return $i+1;
        }
    }
    return false;
}
var_dump(check_order($arr,1));

结果:
int(1)

//二分查找算法
$arr = array(1,3,6,8,23,68,100);
function check_break($arr,$res){
    //1.得到数组的边界(长度)
    $right = count($arr);
    $left = 0;
    //2. 循环匹配
    while($left<=$right){
        //3.得到中间位置
        $middle = floor(($right+$left)/2);
        //4.匹配数据
        if($arr[$middle]==$res){
            return $middle+1;
        }
        //5.没有找到
        if($arr[$middle]<$res){
            //值在右边
            $left=$middle+1;
        }else{
            //值在左边
            $right = $middle-1;
        }
    }
    return false;
}
var_dump(check_break($arr,3));
结果:
float(2)