当前位置:首页 > PHP教程 > php应用 > 列表

PHP常用的排序和查找算法

发布:smiling 来源: PHP粉丝网  添加日期:2021-06-15 20:48:22 浏览: 评论:0 

这篇文章主要介绍了PHP四种基本排序算法和两种查找算法示例,本文用一个实例讲解冒泡排序法、快速排序法、选择排序法、插入排序法的使用,需要的朋友可以参考下。

本文汇总了常见的php排序算法和查找,在进行算法设计的时候有不错的借鉴价值,现分享给大家供参考之用,具体如下:

  1. <?php 
  2. /** 
  3.  * PHP最常用的四个排序方法及二种查找方法 
  4.  * 下面的排序方法全部都通过测试 
  5.  * auther : soulence 
  6.  * date : 2015/06/20 
  7.  */ 
  8.    
  9. //PHP冒泡排序法 
  10. function bubbleSort(&$arr){ 
  11.  //这是一个中间变量 
  12.  $temp=0; 
  13.  //我们要把数组,从小到大排序 
  14.  //外层循环 
  15.  $flag=false;//这个优化之后效率会很高,一般够用 
  16.  for($i=0;$i<count($arr)-1;$i++){ 
  17.     
  18.    for($j=0;$j<count($arr)-1-$i;$j++){ 
  19.      //说明前面的数比后面的数大,就要交换 
  20.      if($arr[$j]>$arr[$j+1]){ 
  21.         $temp=$arr[$j]; 
  22.         $arr[$j]=$arr[$j+1]; 
  23.         $arr[$j+1]=$temp
  24.         $flag=true; 
  25.      } 
  26.    } 
  27.    if(!$flag){ 
  28.     //已经是有序了 
  29.     break
  30.    } 
  31.    $flag=false; 
  32.   } 
  33.    
  34. //PHP选择排序法  效率比冒泡要高 
  35. function selectSort(&$arr){ 
  36.   $temp=0; 
  37.   for($i=0;$i<count($arr)-1;$i++){ 
  38.     //假设$i就是最小的数 
  39.     $minVal=$arr[$i]; 
  40.     //记录我认为的最小数的下标 
  41.     $minIndex=$i
  42.     for($j=$i+1;$j<count($arr);$j++){ 
  43.       //说明我们认为的最小值,不是最小 
  44.       if($minVal>$arr[$j]){ 
  45.          $minVal=$arr[$j]; 
  46.          $minIndex=$j
  47.       } 
  48.     } 
  49.     //最后交换 
  50.     $temp=$arr[$i]; 
  51.     $arr[$i]=$arr[$minIndex]; 
  52.     $arr[$minIndex]=$temp
  53.   } 
  54.    
  55. //插入排序法(小到大排序)  效率又比 选择排序法要高一些 
  56. function insertSort(&$arr){ 
  57.   //先默认下标为0的这个数已经是有序 
  58.   for($i=1;$i<count($arr);$i++){ 
  59.     //$insertVal是准备插入的数 
  60.     $insertVal=$arr[$i]; 
  61.     //准备先和谁下标为$inserIndex的比较 
  62.     $inserIndex=$i-1; 
  63.     //如果这个条件满足,说明我们还没有找到适当的位置 
  64.     while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){ 
  65.     //同时把数后移 
  66.       $arr[$inserIndex+1] = $arr[$inserIndex]; 
  67.       $inserIndex--; 
  68.     } 
  69.     //插入(这时就给$inserIndex找到适当的位置) 
  70.     $arr[$inserIndex+1] = $insertVal
  71.   } 
  72.    
  73.     
  74. //快速排序法 第一种写法 不是我实现的 
  75. function quickSort($left,$right,&$arr){ 
  76.    $l=$left
  77.    $r=$right
  78.    $pivot$arr[($left+$right)/2]; 
  79.    while($l<$r){ 
  80.      while($arr[$l]<$pivot){ 
  81.       $l++; 
  82.      } 
  83.      while($arr[$r]>$pivot){ 
  84.       $r--; 
  85.      } 
  86.      if($l>=$r){ 
  87.       break
  88.      } 
  89.        
  90.      $temp=$arr[$l]; 
  91.      $arr[$l]=$arr[$r]; 
  92.      $arr[$r]=$temp
  93.      if($arr[$l]==$pivot){ 
  94.       --$r
  95.      } 
  96.      if($arr[$r]==$pivot){ 
  97.       ++$l
  98.      } 
  99.    } 
  100.    if($l==$r){ 
  101.     $l++; 
  102.     $r--; 
  103.    } 
  104.    if($left<$r) quickSort($left,$r,$arr); 
  105.    if($right>$l) quickSort($l,$right,$arr); 
  106.    
  107. /** 
  108.  * 快速排序方法 第二种实现方法 自己实现的 
  109.  * PHP快速排序方法 
  110.  * $order asc 小到大 desc大到小 默认是asc 
  111.  * $order 的值只能为 asc desc 如果乱写一个值也是按asc排序的 
  112.  */ 
  113. function quickSort2($arr,$order = 'asc'
  114.  if(count($arr) <= 1) 
  115.   return $arr
  116.    
  117.  $arr_left = $arr_right = array(); 
  118.    
  119.  $val = $arr[0];unset($arr[0]); 
  120.    
  121.  foreach ($arr as $v) { 
  122.   if(strtolower($order) == 'desc'){ 
  123.    if($v < $val
  124.     $arr_right[] = $v
  125.    else 
  126.     $arr_left[] = $v
  127.   }else
  128.    if($v > $val
  129.     $arr_right[] = $v
  130.    else 
  131.     $arr_left[] = $v
  132.   } 
  133.  } 
  134.    
  135.  $arr_left = quickSort($arr_left,$order); 
  136.  $arr_right = quickSort($arr_right,$order); 
  137.    
  138.  return array_merge($arr_left,array($val),$arr_right); 
  139.    
  140.    
  141. //下面是查找 
  142. $arr=array(46,90,900,0,-1); 
  143. //这是按顺序查询 
  144. function search(&$arr,$findVal){    
  145.   $flag=false; 
  146.   for($i=0;$i<count($arr);$i++){ 
  147.     if($findVal==$arr[$i]){ 
  148.       echo "找到了,下标为=$i"
  149.       $flag=true; 
  150.       //查询一次,如果多次就不要这个 break; 
  151.     } 
  152.   } 
  153.   if(!$flag){ 
  154.     echo "查无此数"
  155.   } 
  156.    
  157. //调用二分查找 
  158. $arr=array(0,90,900,99990);//注意,一定要是有序的 
  159. binarySwarch($arr,90,0,count($arr)-1); 
  160.    
  161. //二分查找函数,它有一个前提,查找的数组必须是有序的 
  162. function binarySearch(&$arr,$findVal,$leftIndex,$rightIndex){ 
  163.   //如果$rightIndex < $leftIndex条件成立,说明没有这个数,则退出 
  164.   if($rightIndex < $leftIndex){ 
  165.     echo "找不到该数"
  166.     return
  167.   } 
  168.   //首先找到中间这个数 round是出于如果出现小数,四舍五入 
  169.   $middleIndex=round(($rightIndex+$leftIndex)/2); 
  170.   //如果大于则向后面找 
  171.   if($findVal > $arr[$middleIndex]){ 
  172.     binarySearch($arr,$findVal,$middleIndex+1,$rightIndex); 
  173.     //如果小于中间数,则向前面找 
  174.   }else if($findVal < $arr[$middleIndex]){ 
  175.     binarySearch($arr,$findVal,$leftIndex,$middleIndex-1); 
  176.   }else
  177.     echo "找到这个数。下标是$middleIndex"
  178.   } 
  179. ?> 

希望本文所述排序算法和查找算法实例对大家的php程序设计有所帮助。

Tags: PHP排序 PHP查找算法

分享到: