PHP实现常见查找和排序算法

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

1、冒泡排序

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

复制代码

2、归并排序

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

复制代码

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 return bin_search($arr,$low,$mid-1,$value);
9. else
10. return bin_search($arr,$mid+1,$high,$value);
11. }
12. }

复制代码

4、二分查找-非递归

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

复制代码

5、快速排序

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

复制代码

6、选择排序

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

复制代码

7、插入排序

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

复制代码