PHP语法初步 算法编程思想 基础知识点笔记整理(八)

编程思想

递推算法

利用特定关系得出中间推论，直至得到结果的算法。。。分为顺推和逆推两种

顺推:通过最简单的条件，逐步推演结果。

逆推，通过结果找到规律，从而推到已知条件。

递归算法

把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数以表达问题的解。

简化问题，找到最优子问题。

递归的本质是函数调用：一个函数需要开辟一块内存，递归会出现同时调用多个函数，故占用很多内存。

冒泡排序

1、比较相邻元素，若前一个比后一个大，则交换。

2、对每一对相邻元素进行1操作，直至最后一对。此时最后一个因为最大值。

3、除最后一个外，重复以上操作

4、重复以上操作，直至排序完成。

<?php

$arr = array(1,3,2,5,9,8,7);
// 计算长度
$len = count($arr);

for($i = 0;$i<$len-1;$i++)    // 第几次重复循环
{
    for($j = 0;$j<$len-$i-1;$j++)  // 第几次交换
    {
        if($arr[$j] > $arr[$j+1])
            swap1($arr[$j],$arr[$j+1]);
    }
}
var_dump($arr);

// 交换值
function swap1(&$a,&$b)
{
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

选择排序

1、假设第一个元素为最小元素，记下下标

2、寻找右侧剩余元素，若有更小的，则记下更小的下标

3、一行对比完成后，交换第一个和最小的元素

4、重新开始以上操作

<?php

$arr = array(1,5,2,5,9,6,3,4);
$min_index = 0;  

$len = count($arr);

for($i = 0; $i<$len-1; $i++)
{
    $min_index = $i;
    for($j = $min_index + 1;$j<$len;$j++)
    {
        if($arr[$min_index] > $arr[$j])
            $min_index = $j;
    }
    if($min_index != $i)
        swap1($arr[$min_index],$arr[$i]);
}
var_dump($arr);

// 交换值
function swap1(&$a,&$b)
{
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

插入排序

1、认定一个第一个元素已经排好序；

2、取出第二个元素作为待插入元素；

3、将待插入元素与已排好元素比较；

4、若小于已排好元素，则说明前面排序未在正确位置，应该向后移动，让新元素插入进去

5、重复以上操作，直到该元素插入完毕

6、重复操作，直至所有元素完毕

<?php
$arr = [4,2,6,8,9,5];

$len = count($arr);

for($i = 1;$i<$len;$i++)   // 第几个元素为待插入元素
{
    $tmp = $arr[$i];
    for($j = $i;$j>0;$j--)  // 比较几次
    {
        if($tmp < $arr[$j-1])    // 注意此处比较的是tmp
            $arr[$j] = $arr[$j-1];
        else
            break;
    }
    if($arr[$j] != $tmp)
        $arr[$j] =$tmp;
}

var_dump($arr);

// 交换值
function swap1(&$a,&$b)
{
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

快速排序法

<?php

$arr = array(1,6,3,4,9,2);

// 定义数组开头及结尾
$start = 0;
$end = count($arr)-1;

// 定义函数作为递归函数
function quick_sort($arr)
{
    // 递归出口
    $len = count($arr);
    if($len <= 1) return $arr;

    // 比较并分散数据
    $left = $right = array();  // 定义空数组用于存放大的或小的
    for($i = 1;$i<$len;$i++)
    {
        if($arr[$i]>$arr[0]) $right[] = $arr[$i];   // 大于存放在右边数组
        else $left[] = $arr[$i];   // 小于存放在左边数组
    }

    // 递归
    $left = quick_sort($left);  // 分别将右数组和左数组进一步排序
    $right = quick_sort($right);

    return array_merge($left,(array)$arr[0],$right);

}

$res = quick_sort($arr);
var_dump($res);   // 不能用echo

<?php

// 快排双指针

$arr = array(1,2,3,9,2,8,7);
function quick_sort($arr)
{
    // 递归结束条件
    $len = count($arr);
    if($len <= 1) return $arr;

    // 定义双指针
    $left = 0;
    $right = $len-1;
    $pivot = $arr[0];  // 确定基准
    while($left < $right)   // left == right时跳出循环
    {
        while($left < $right && $arr[$right] >= $pivot) $right--;
        while($left < $right && $arr[$left] <= $pivot) $left++;
        swap1($arr[$left],$arr[$right]);
    }
    swap1($arr[$left],$arr[0]);   // 跳出循环时，left = right ，故将pivot赋值即可

    // 递归点(上述操作完毕后，需要进一步排序左边和右边，故需递归)
    $left_arr = quick_sort(array_slice($arr,0,$left));
    $right_arr = quick_sort(array_slice($arr,$left+1));

    return array_merge($left_arr,(array)$arr[$left],$right_arr);
}

var_dump(quick_sort($arr));

// 交换值
function swap1(&$a,&$b)
{
    $tmp = $a;
    $a = $b;
    $b = $tmp;
}

归并排序

<?php

// 二路合并算法
$arr1 = array(1,2,5,6);
$arr2 = array(3,7,8,9);

$res = array();    // 存合并后的元素

while(count($arr1) && count($arr2))
{
    $res[] = $arr1[0]>$arr2[0] ? array_shift($arr2):array_shift($arr1);
}
while(count($arr1) && !count($arr2))
{
    $res[] = array_shift($arr1);
}
while(count($arr2) && !count($arr1))
{
    $res[] = array_shift($arr2);
}

var_dump($res);

1、将数组拆分成两个数组

2、重复步骤1，将数组拆分成最小单元

3、然后二路归并

4、重复步骤直至完成

<?php

// 归并排序

$arr = array(1,15,7,9,8,6,2,3,4);

function merge_sort($arr)
{
    // 1、递归结束条件
    $len = count($arr);
    if($len <= 1) return $arr;

    // 2、重复的操作
    // 2、1 拆分数组
    $middle = $len>>1;
    $left = array_slice($arr,0,$middle);
    $right = array_slice($arr,$middle);

    // 4、递归点（最后写这一步，先将一层的分离和合并写完，再找递归点）
    $left = merge_sort($left);
    $right = merge_sort($right);
    // 2、2 二路归并
    $res = array();    // 存合并后的元素

    while(count($left) && count($right))
    {
        $res[] = $left[0]>$right[0] ? array_shift($right):array_shift($left);
    }
    while(count($left) && !count($right))
    {
        $res[] = array_shift($left);
    }
    while(count($right) && !count($left))
    {
        $res[] = array_shift($right);
    }

    // 3、返回值
    return array_merge($res);
}

var_dump(merge_sort($arr));

查找算法

<?php

$arr = array(1,3,6,17,24,31,32);
// 顺序查找：从数组第一个元素开始挨个匹配
function find_index($arr,$num)
{
    foreach($arr as $k => $v)
    {
        if($v == $num) return $k;
    }
    return false;
}

// var_dump(find_index($arr,2));  // 不存在，故返回bool(false)
// var_dump(find_index($arr,32));  // 存在，故返回int(5)

function Binary_search($arr,$num)
{
    $len = count($arr);
    $left = 0;
    $right = $len-1;

    while($left <= $right)
    {
        $middle = $left+($right-$left>>1);
        if($arr[$middle] > $num) 
            $right = $middle-1;
        elseif($arr[$middle] < $num) 
            $left = $middle+1;
        else 
            return $middle;
    }

    return false;
}
print_r(Binary_search($arr,6));
var_dump(Binary_search($arr,2));