PHP算法分析

偶然间在网上看到了一篇文章《程序员必须知道的10大基础实用算法及其讲解》，发现一个不懂算法的程序猿算不上一个合格的猿，所以接下来的目标又多出了一个算法和数据结构。

本文的算法全部使用PHP语言实现。

1.快速排序算法

在我看来快速排序就是先找到一个基准，然后创建两个数组，把大于这个基准的数字放到一个数组里，小于这个基准的数字放到一个数组里，然后在两个数组里分别再进行判断。

具体实现：

[php] view plain copy

print?

1. <?php  
2.     function quickSort(&$arr) {  
3.         if(count($arr)>1) {  
4.             $k = $arr[0];  
5.             $x = array();  
6.             $y = array();  
7.             $_size = count($arr);  
8.             for($i=1;$i<$_size;$i++) {  
9.                 if($arr[$i]<=$k) {  
10.                     $x[] = $arr[$i];  
11.                 }elseif($arr[$i]>$k) {  
12.                     $y[] = $arr[$i];  
13.                 }  
14.             }  
15.             $x = quickSort($x);  
16.             $y = quickSort($y);  
17.             return array_merge($x,array($k),$y);  
18.         }else {  
19.             return $arr;  
20.         }  
21.     }  
22. ?>  

2.二分查找算法

二分查找用于从一个数组中查找一个元素所在位置的算法。原理是，首先对数组进行排序，然后取这个数组的中间值和目标元素进行判断，如果目标元素小于中间值，那么它就在中间值的前半部分，然后再从前半部分应用二分查找。

具体实现：

[php] view plain copy

print?

1. <?php  
2.     function binarySearch(Array $arr,$target) {  
3.         $low = 0;  
4.         $high = count($arr)-1;  
5.         while($low<=$high) {  
6.             $mid = floor(($low+$high)/2);  
7.             if($arr[$mid]==$target) {  
8.                 //找到了  
9.                 return $mid;  
10.             }  
11.             if($arr[$mid] < $target) {  
12.                 //中间值小于目标值，搜索后半部分  
13.                 $low = $mid+1;  
14.             }  
15.             if($arr[$mid] > $target) {  
16.                 //中间值大于目标值，搜索前半部分  
17.                 $high = $mid-1;  
18.             }  
19.         }  
20.         //查找失败  
21.         return false;  
22.     }  
23. ?>  

3.值传递和引用传递（插一句）

有时候我们看到的函数是这样的

[php] view plain copy

print?

1. function bubbleSort(&$arr) {  
2.     $arr++;  
3. }  

那么传递的$arr到底是怎么回事呢，其实这就是php中的引用传递方法。

例如：

[php] view plain copy

print?

1. function bubbleSort($num) {  
2.     $num++;  
3. }  
4. function bubbleSort1(&$num) {  
5.     $num++;  
6. }  
7. $num = 1;  
8. echo "num=".$num."<br/>";  
9. bubbleSort($num);  
10. echo "bubbleSort-num=".$num."<br/>";  
11. bubbleSort1($num);  
12. echo "bubbleSort1-num=".$num."<br/>";  

输出结果：

num=1
bubbleSort-num=1
bubbleSort1-num=2

会发现，使用值传递的时候，并不会改变传入参数的值。而使用引用传递的时候，会将传入参数的值改变。

4.冒泡排序

每一次循环，比较相邻两个元素，实现找到最大的元素放在最后，像冒泡一样，每次循环冒上去一个最大的元素，所以叫冒泡排序吧，哈哈哈！

具体实现：

[php] view plain copy

print?

1. function bubbleSort($arr = array()) {  
2.     $size = count($arr);  
3.     for($i = 0; $i < $size - 1; $i++) {  
4.         for($j = $i + 1; $j < $size; $j++) {  
5.             if($arr[$i] > $arr[$j]) {  
6.                 $tmp = $arr[$i];  
7.                 $arr[$i] = $arr[$j];  
8.                 $arr[$j] = $tmp;  
9.             }  
10.         }  
11.     }  
12.     return $arr;  
13. }  
14. $test = array(3,2,1,5,9,7,4,12,10);  
15. print_r(bubbleSort($test));