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