常用算法PHP版-面试必备

算法这个东西，研究起来的确很费劲，牵涉的东西太多。至于PHP程序员，能掌握最好，虽然实际工作中用的不是很多。不过，面试时必不可少。

下面分享一些最常见的算法，用PHP如何实现。

1、冒泡排序

1. function bubble_sort($arr) {
2. $n=count($arr);
3. for($i=0;$i<$n-1;$i++){
4. for($j=$i+1;$j<$n;$j++) {
5. if($arr[$j]<$arr[$i]) {
6. $temp=$arr[$i];
7. $arr[$i]=$arr[$j];
8. $arr[$j]=$temp;
9. }
10. }
11. }
12. return $arr;
13. }

2、归并排序

1. function Merge(&$arr, $left, $mid, $right) {
2. $i = $left;
3. $j = $mid + 1;
4. $k = 0;
5. $temp = array();
6. while ($i <= $mid && $j <= $right)
7. {
8. if ($arr[$i] <= $arr[$j])
9. $temp[$k++] = $arr[$i++];
10. else
11. $temp[$k++] = $arr[$j++];
12. }
13. while ($i <= $mid)
14. $temp[$k++] = $arr[$i++];
15. while ($j <= $right)
16. $temp[$k++] = $arr[$j++];
17. for ($i = $left, $j = 0; $i <= $right; $i++, $j++)
18. $arr[$i] = $temp[$j];
19. }
20.  
21. function MergeSort(&$arr, $left, $right)
22. {
23. if ($left < $right)
24. {
25. $mid = floor(($left + $right) / 2);
26. MergeSort($arr, $left, $mid);
27. MergeSort($arr, $mid + 1, $right);
28. Merge($arr, $left, $mid, $right);
29. }
30. }

3、二分查找-递归

1. function bin_search($arr,$low,$high,$value) {
2. if($low>$high)
3. return false;
4. else {
5. $mid=floor(($low+$high)/2);
6. if($value==$arr[$mid])
7. return $mid;
8. elseif($value<$arr[$mid])
9. return bin_search($arr,$low,$mid-1,$value);
10. else
11. return bin_search($arr,$mid+1,$high,$value);
12. }
13. }

4、二分查找-非递归

1. function bin_search($arr,$low,$high,$value) {
2. while($low<=$high) {
3. $mid=floor(($low+$high)/2);
4. if($value==$arr[$mid])
5. return $mid;
6. elseif($value<$arr[$mid])
7. $high=$mid-1;
8. else
9. $low=$mid+1;
10. }
11. return false;
12. }

5、快速排序

1. function quick_sort($arr) {
2. $n=count($arr);
3. if($n<=1)
4. return $arr;
5. $key=$arr[0];
6. $left_arr=array();
7. $right_arr=array();
8. for($i=1;$i<$n;$i++) {
9. if($arr[$i]<=$key)
10. $left_arr[]=$arr[$i];
11. else
12. $right_arr[]=$arr[$i];
13. }
14. $left_arr=quick_sort($left_arr);
15. $right_arr=quick_sort($right_arr);
16. return array_merge($left_arr,array($key),$right_arr);
17. }

6、选择排序

1. function select_sort($arr) {
2. $n=count($arr);
3. for($i=0;$i<$n;$i++) {
4. $k=$i;
5. for($j=$i+1;$j<$n;$j++) {
6. if($arr[$j]<$arr[$k])
7. $k=$j;
8. }
9. if($k!=$i) {
10. $temp=$arr[$i];
11. $arr[$i]=$arr[$k];
12. $arr[$k]=$temp;
13. }
14. }
15. return $arr;
16. }

7、插入排序

1. function insertSort($arr) {
2. $n=count($arr);
3. for($i=1;$i<$n;$i++) {
4. $tmp=$arr[$i];
5. $j=$i-1;
6. while($arr[$j]>$tmp) {
7. $arr[$j+1]=$arr[$j];
8. $arr[$j]=$tmp;
9. $j--;
10. if($j<0)
11. break;
12. }
13. }
14. return $arr;
15. }

原文地址：http://blog.phpha.com/archives/782.html