PHP常见算法

排序

冒泡排序

依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

$arr = [8,1,10,9,5,7];function bubbleSort($arr){    // 外层 for 循环控制循环次数    for ($i=0; $i<count($arr) ; $i++) {        //内层 for 循环进行两数交换，找每次的最大数，排到最后        for ($j=0; $j < count($arr)-1; $j++) {            //数组里第一个和第二个对比，如果1>2，执行数值互换            if($arr[$j] >$arr[$j+1]){   $x = $arr[$j];  //第一赋给一个变量                $arr[$j] = $arr[$j+1]; //第二赋给第一                $arr[$j+1] = $x;  //把变量给第二，结果就是1，2的数值互换                // $a=10;                // $b=20;                // $x=$a; $x=10                // $a=$b; $a=20                // $b=$X; $b=10            }        }    }    return $arr;}print_r(bubbleSort($arr));

快速排序

快速排序是对冒泡排序的一种改进。
设置一个基准元素，通过排序将需要排序的数据分割成两个部分，其中一部分的所有数据比基准元素小，另一部分的所有数据比基准元素大，然后对这两部分数据分别进行递归快速排序，最后将得到的数据和基准元素进行合并，就得到了所需数据。

$arr = [8,1,10,9,5,7];function quickSort($arr){    $lenth = count($arr);//获取数组个数    if($lenth <= 1){//小于等于一个不用往下走了        return $arr;    }    //选择基准元素。一般选第一个或最后一个    $first = $arr[0];    $left = array();//接收小于基准元素的值    $right = array();//接收大于基准元素的值    //循环从1开始，因为基准元素是0    for($i=1;$i<$lenth;$i++){        if($arr[$i]<$first){//小于基准元素的值            $left[] = $arr[$i];        }else{//大于基准元素的值            $right[] = $arr[$i];        }    }    //递归排序    $left = quickSort($left);    $right = quickSort($right);    //合并返回数组    return array_merge($left,array($first),$right);}print_r(quickSort($arr));

选择排序

找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置；
2.在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置;
3.如此循环，直到整个数组排序完成。

$arr = [8,1,10,9,5,7];function selectSort($arr){    //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数，$i 当前最小值的位置， 需要参与比较的元素    for($i=0, $len=count($arr); $i<$len-1; $i++){        //先假设最小的值的位置        $p = $i;        //$j 当前都需要和哪些元素比较，$i 后边的。        for($j=$i+1; $j<$len; $j++) {            //$arr[$p] 是 当前已知的最小值            if($arr[$p] > $arr[$j]){                //比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。                $p = $j;            }        }        //已经确定了当前的最小值的位置，保存到$p中。如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可。        if($p != $i){            $tmp = $arr[$p];            $arr[$p] = $arr[$i];            $arr[$i] = $tmp;        }    }     return $arr;}print_r(selectSort($arr));

插入排序

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

$arr = [8,1,10,9,5,7];function insertSort($arr){    $count = count($arr);       for($i=1; $i<$count; $i++){                 $tmp = $arr[$i];                $j = $i - 1;                while(isset($arr[$j]) && $arr[$j] > $tmp){                         $arr[$j+1] = $arr[$j];                      $arr[$j] = $tmp;                        $j--;                   }        }        return $arr; } print_r(insertSort($arr));

希尔排序

希尔排序(shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

$arr = [8,1,10,9,5,7];function shellSort(&$arr){    if(!is_array($arr))return;$n=count($arr);    for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2)){        for($i=$gap;$i<$n;++$i){            for($j=$i-$gap;$j>=0&&$arr[$j+$gap]<$arr[$j];$j-=$gap){                $temp=$arr[$j];                $arr[$j]=$arr[$j+$gap];                $arr[$j+$gap]=$temp;            }        }    }    return $arr;}print_r(shellSort($arr));

查找

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

function binarySearch($array, $findVal){    // 非数组或者数组为空，直接返回-1    if (!is_array($array) || empty($array)) {        return -1;    }    // 查找区间，起点和终点    $start = 0;    $end = count($array) - 1;    while ($start <= $end) {        // 以中间点作为参照点比较，取整数        $middle = intval(($start + $end) / 2);         if ($array[$middle] > $findVal) {            // 查找数比参照点小，则要查找的数在左半边            // 因为 $middle 已经比较过了，这里需要减1            $end = $middle - 1;         } elseif ($array[$middle] < $findVal) {            // 查找数比参照点大，则要查找的数在右半边            // 因为 $middle 已经比较过了，这里需要加1            $start = $middle + 1;         } else {            // 查找数与参照点相等，则找到返回            return $middle;        }    }    // 未找到，返回-1    return -1;} // 调用$array = [10,12,16,19,20,34,56,78,84,95,100];echo binarySearch($array, 84);function binSearch($array, $findVal, $start, $end){    // 以中间点作为参照点比较，取整数    $middle = intval(($start + $end) / 2);    if ($start > $end) {        return -1;    }    if ($findVal > $array[$middle]) {        // 查找数比参照点大，则要查找的数在右半边        return binSearch($array, $findVal, $middle + 1, $end);     } elseif ($findVal < $array[$middle]) {        // 查找数比参照点小，则要查找的数在左半边        return binSearch($array, $findVal, $start, $middle - 1);     } else {        return $middle;    }} // 调用$arr = [10,12,16,19,20,34,56,78,84,95,100];var_dump(binSearch($arr, 95, 0, count($arr)-1));

ps：未完待续

来源地址：https://blog.csdn.net/heshihu2019/article/details/132699273