PHP常用排序与查找算法实现详解

PHP排序算法实现

第1步：使用冒泡排序法进行数组排序

目的：通过相邻元素比较交换，将数组从小到大排列。该算法包含优化标志位，若无交换则提前结束。

操作说明：调用 bubbleSort(&$arr) 函数，传入引用数组。算法外层循环控制轮数，内层循环比较相邻项。若前项大于后项则交换，并标记 $flag=true；若一轮内无交换，则跳出循环。

<?php
function bubbleSort(&$arr){
 $temp=0;
 $flag=false;
 for($i=0;$i<count($arr)-1;$i++){
   for($j=0;$j<count($arr)-1-$i;$j++){
     if($arr[$j]>$arr[$j+1]){
        $temp=$arr[$j];
        $arr[$j]=$arr[$j+1];
        $arr[$j+1]=$temp;
        $flag=true;
     }
   }
   if(!$flag){
    break;
   }
   $flag=false;
  }
}

第2步：使用选择排序法优化性能

目的：相比冒泡排序，减少交换次数，提高效率。每次从未排序部分选出最小值放到已排序部分的末尾。

操作说明：调用 selectSort(&$arr)。遍历数组假设当前索引为最小值，内层循环寻找实际最小值的下标 $minIndex 和值 $minVal，最后执行一次交换操作。

<?php
function selectSort(&$arr){
  $temp=0;
  for($i=0;$i<count($arr)-1;$i++){
    $minVal=$arr[$i];
    $minIndex=$i;
    for($j=$i+1;$j<count($arr);$j++){
      if($minVal>$arr[$j]){
         $minVal=$arr[$j];
         $minIndex=$j;
      }
    }
    $temp=$arr[$i];
    $arr[$i]=$arr[$minIndex];
    $arr[$minIndex]=$temp;
  }
}

第3步：使用插入排序法处理有序子序列

目的：将未排序元素逐个插入到已排序部分的正确位置。对于小规模或部分有序数据效率较高。

操作说明：调用 insertSort(&$arr)。从第二个元素开始，取出待插入值 $insertVal，在已排序区间内从后向前扫描，若发现比 $insertVal 大的数则向后移动，直到找到合适位置插入。

<?php
function insertSort(&$arr){
  for($i=1;$i<count($arr);$i++){
    $insertVal=$arr[$i];
    $inserIndex=$i-1;
    while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){
      $arr[$inserIndex+1] = $arr[$inserIndex];
      $inserIndex--;
    }
    $arr[$inserIndex+1] = $insertVal;
  }
}

第4步：使用快速排序法进行高效分区排序

目的：利用分治思想，选择一个基准值将数组分为两部分递归排序。适用于大规模数据。

操作说明：可使用标准写法 quickSort($left,$right,&$arr)，通过双指针向中间收缩交换元素；或使用第二种实现 quickSort2($arr,$order='asc')，该方法支持指定升序(asc)或降序(desc)，通过递归合并左右子数组。

<?php
//标准写法
function quickSort($left,$right,&$arr){
   $l=$left;
   $r=$right;
   $pivot= $arr[($left+$right)/2];
   while($l<$r){
     while($arr[$l]<$pivot){ $l++; }
     while($arr[$r]>$pivot){ $r--; }
     if($l>=$r){ break; }
     $temp=$arr[$l];
     $arr[$l]=$arr[$r];
     $arr[$r]=$temp;
     if($arr[$l]==$pivot){ --$r; }
     if($arr[$r]==$pivot){ ++$l; }
   }
   if($l==$r){ $l++; $r--; }
   if($left<$r) quickSort($left,$r,$arr);
   if($right>$l) quickSort($l,$right,$arr);
}

//支持升降序的写法
function quickSort2($arr,$order = 'asc'){
 if(count($arr) <= 1)
  return $arr;
 $arr_left = $arr_right = array();
 $val = $arr[0];unset($arr[0]);
 foreach ($arr as $v) {
  if(strtolower($order) == 'desc'){
   if($v < $val) $arr_right[] = $v;
   else $arr_left[] = $v;
  }else{
   if($v > $val) $arr_right[] = $v;
   else $arr_left[] = $v;
  }
 }
 $arr_left = quickSort($arr_left,$order); //注意此处需确保递归调用正确，原稿可能存在逻辑嵌套差异，建议统一使用quickSort2内部递归或修正
 $arr_right = quickSort2($arr_right,$order);
 return array_merge($arr_left,array($val),$arr_right);
}

PHP查找算法实现

第5步：使用顺序查找检测元素是否存在

目的：在不要求数组有序的情况下，线性遍历查找目标值。

操作说明：调用 search(&$arr,$findVal)。遍历数组，若发现相等元素则输出下标并可选退出；若遍历完未找到，输出“查无此数”。

<?php
function search(&$arr,$findVal){   
  $flag=false;
  for($i=0;$i<count($arr);$i++){
    if($findVal==$arr[$i]){
      echo "找到了，下标为=$i";
      $flag=true;
      //如需单次查找可添加 break;
    }
  }
  if(!$flag){
    echo "查无此数";
  }
}

第6步：使用二分查找提高有序数组检索速度

前提条件：查找数组必须是有序的。

目的：通过折半比较，每次排除一半数据，显著降低查找时间复杂度。

操作说明：调用 binarySearch(&$arr,$findVal,$leftIndex,$rightIndex)。计算中间下标 $middleIndex，若目标值大于中间值则在右半部分继续查找，小于则在左半部分，相等则返回下标。若左右索引交错则判定不存在。

<?php
$arr=array(0,90,900,99990);
binarySearch($arr,90,0,count($arr)-1);

function binarySearch(&$arr,$findVal,$leftIndex,$rightIndex){
  if($rightIndex < $leftIndex){
    echo "找不到该数";
    return;
  }
  $middleIndex=round(($rightIndex+$leftIndex)/2);
  if($findVal > $arr[$middleIndex]){
    binarySearch($arr,$findVal,$middleIndex+1,$rightIndex);
  }else if($findVal < $arr[$middleIndex]){
    binarySearch($arr,$findVal,$leftIndex,$middleIndex-1);
  }else{
    echo "找到这个数。下标是$middleIndex";
  }
}

以上就是PHP常用的排序和查找算法实现的详细内容，更多关于PHP算法设计的资料请关注本站其它相关文章！