首页 > 开发 > PHP > 正文

PHP常用的排序和查找算法

2024-05-04 23:38:34
字体:
来源:转载
供稿:网友

这篇文章主要介绍了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. if(!$flag){ 
  26. //已经是有序了 
  27. break
  28. $flag=false; 
  29.  
  30. //PHP选择排序法 效率比冒泡要高 
  31. function selectSort(&$arr){ 
  32. $temp=0; 
  33. for($i=0;$i<count($arr)-1;$i++){ 
  34. //假设$i就是最小的数 
  35. $minVal=$arr[$i]; 
  36. //记录我认为的最小数的下标 
  37. $minIndex=$i
  38. for($j=$i+1;$j<count($arr);$j++){ 
  39. //说明我们认为的最小值,不是最小 
  40. if($minVal>$arr[$j]){ 
  41. $minVal=$arr[$j]; 
  42. $minIndex=$j
  43. //最后交换 
  44. $temp=$arr[$i]; 
  45. $arr[$i]=$arr[$minIndex]; 
  46. $arr[$minIndex]=$temp
  47.  
  48. //插入排序法(小到大排序) 效率又比 选择排序法要高一些 
  49. function insertSort(&$arr){ 
  50. //先默认下标为0的这个数已经是有序 
  51. for($i=1;$i<count($arr);$i++){ 
  52. //$insertVal是准备插入的数 
  53. $insertVal=$arr[$i]; 
  54. //准备先和谁下标为$inserIndex的比较 
  55. $inserIndex=$i-1; 
  56. //如果这个条件满足,说明我们还没有找到适当的位置 
  57. while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){ 
  58. //同时把数后移 
  59. $arr[$inserIndex+1] = $arr[$inserIndex]; 
  60. $inserIndex--; 
  61. //插入(这时就给$inserIndex找到适当的位置) 
  62. $arr[$inserIndex+1] = $insertVal
  63.  
  64.  
  65. //快速排序法 第一种写法 不是我实现的 
  66. function quickSort($left,$right,&$arr){ 
  67. $l=$left
  68. $r=$right
  69. $pivot$arr[($left+$right)/2]; 
  70. while($l<$r){ 
  71. while($arr[$l]<$pivot){ 
  72. $l++; 
  73. while($arr[$r]>$pivot){ 
  74. $r--; 
  75. if($l>=$r){ 
  76. break
  77.  
  78. $temp=$arr[$l]; 
  79. $arr[$l]=$arr[$r]; 
  80. $arr[$r]=$temp
  81. if($arr[$l]==$pivot){ 
  82. --$r
  83. if($arr[$r]==$pivot){ 
  84. ++$l
  85. if($l==$r){ 
  86. $l++; 
  87. $r--; 
  88. if($left<$r) quickSort($left,$r,$arr); 
  89. if($right>$l) quickSort($l,$right,$arr); 
  90.  
  91. /** 
  92. * 快速排序方法 第二种实现方法 自己实现的 
  93. * PHP快速排序方法 
  94. * $order asc 小到大 desc大到小 默认是asc 
  95. * $order 的值只能为 asc desc 如果乱写一个值也是按asc排序的 
  96. */ 
  97. function quickSort2($arr,$order = 'asc'
  98. if(count($arr) <= 1) 
  99. return $arr
  100.  
  101. $arr_left = $arr_right = array(); 
  102.  
  103. $val = $arr[0];unset($arr[0]); 
  104.  
  105. foreach ($arr as $v) { 
  106. if(strtolower($order) == 'desc'){ 
  107. if($v < $val
  108. $arr_right[] = $v
  109. else 
  110. $arr_left[] = $v
  111. }else
  112. if($v > $val
  113. $arr_right[] = $v
  114. else 
  115. $arr_left[] = $v
  116.  
  117. $arr_left = quickSort($arr_left,$order); 
  118. $arr_right = quickSort($arr_right,$order); 
  119.  
  120. return array_merge($arr_left,array($val),$arr_right); 
  121.  
  122.  
  123. //下面是查找 
  124. $arr=array(46,90,900,0,-1); 
  125. //这是按顺序查询 
  126. function search(&$arr,$findVal){  
  127. $flag=false; 
  128. for($i=0;$i<count($arr);$i++){ 
  129. if($findVal==$arr[$i]){ 
  130. echo "找到了,下标为=$i"
  131. $flag=true; 
  132. //查询一次,如果多次就不要这个 break; 
  133. if(!$flag){ 
  134. echo "查无此数"
  135.  
  136. //调用二分查找 
  137. $arr=array(0,90,900,99990);//注意,一定要是有序的 
  138. binarySwarch($arr,90,0,count($arr)-1); 
  139.  
  140. //二分查找函数,它有一个前提,查找的数组必须是有序的 
  141. function binarySearch(&$arr,$findVal,$leftIndex,$rightIndex){ 
  142. //如果$rightIndex < $leftIndex条件成立,说明没有这个数,则退出 
  143. if($rightIndex < $leftIndex){ 
  144. echo "找不到该数"
  145. return
  146. //首先找到中间这个数 round是出于如果出现小数,四舍五入 
  147. $middleIndex=round(($rightIndex+$leftIndex)/2); 
  148. //如果大于则向后面找 
  149. if($findVal > $arr[$middleIndex]){ 
  150. binarySearch($arr,$findVal,$middleIndex+1,$rightIndex); 
  151. //如果小于中间数,则向前面找 
  152. }else if($findVal < $arr[$middleIndex]){ 
  153. binarySearch($arr,$findVal,$leftIndex,$middleIndex-1); 
  154. }else
  155. echo "找到这个数。下标是$middleIndex"
  156. ?> 

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

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表