当前位置:Gxlcms > PHP教程 > PHP实现常见查找和排序算法

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

时间:2021-07-01 10:21:17 帮助过:20人阅读

下面分享一些最常见的算法,用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. function MergeSort(&$arr, $left, $right)
  21. {
  22. if ($left < $right)
  23. {
  24. $mid = floor(($left + $right) / 2);
  25. MergeSort($arr, $left, $mid);
  26. MergeSort($arr, $mid + 1, $right);
  27. Merge($arr, $left, $mid, $right);
  28. }
  29. }

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. }

人气教程排行