php四种基础算法

PHP 的四种基础算法主要包括：

1、排序算法

2、查找算法

3、递归算法

4、分治算法

排序算法

排序算法主要用于对数据进行排序，比如从小到大或者从大到小，在 PHP 中，常见的排序算法有冒泡排序、选择排序、插入排序等。

冒泡排序

冒泡排序的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

function bubbleSort($arr){
    $len = count($arr);
    for($i=0;$i<$len1;$i++){
        for($j=$i+1;$j<$len;$j++){
            if($arr[$i]>$arr[$j]){
                $tmp = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
    return $arr;
}

查找算法

查找算法主要用于在数据集中查找特定的数据，在 PHP 中，常见的查找算法有线性查找和二分查找。

二分查找

二分查找是一种效率较高的查找方法，要求数据集已经按照大小顺序排列，其基本思想是：首先确定数据集的中间位置，然后将待查找的值与中间位置的值进行比较，如果相等则查找成功；如果待查找的值小于中间位置的值，则在数据集的前半部分继续查找；如果待查找的值大于中间位置的值，则在数据集的后半部分继续查找，如此循环，直到找到待查找的值，或者查找范围为空。

function binarySearch($arr, $target){
    $left = 0;
    $right = count($arr) 1;
    while($left <= $right){
        $mid = floor(($left + $right) / 2);
        if($arr[$mid] == $target){
            return $mid;
        }else if($arr[$mid] > $target){
            $right = $mid 1;
        }else{
            $left = $mid + 1;
        }
    }
    return 1;
}

递归算法

递归算法是一种利用函数自身调用自身来解决问题的方法，在 PHP 中，常见的递归算法有计算阶乘、斐波那契数列等。

计算阶乘

阶乘是一个正整数n的所有小于及等于n的正整数的积，记作n!，例如5!=5*4*3*2*1，使用递归的方式实现阶乘，就是当n>1时，n!=n*(n1)!。

function factorial($n){
    if($n == 1){
        return 1;
    }else{
        return $n * factorial($n 1);
    }
}

分治算法

分治算法是一种解决问题的策略，它将一个大问题分解为若干个小问题，然后分别解决这些小问题，最后将这些小问题的解合并成大问题的解，在 PHP 中，常见的分治算法有归并排序、快速排序等。

快速排序

快速排序是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

function quickSort($arr){
    if(count($arr)<=1){
        return $arr;
    }
    $pivot = $arr[0];
    $left = $right = [];
    foreach($arr as $k=>$v){
        if($v<$pivot){
            $left[] = $v;
        }else{
            $right[] = $v;
        }
    }
    return array_merge(quickSort($left),[$pivot],quickSort($right));
}