排序
冒泡排序
依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。
$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