PHP-常见算法

1:请写出常见的排序算法,并用PHP实现冒泡排序,将数组按照从小到大的方式进行排序

冒泡排序的原理和实现

• 原理:两辆相邻的数进行比较,如过反序就交换,否则将就不交换
• 时间复杂度:最坏(O(n^2)),平均(O(n^2))
• 空间复杂度:O(1)
  

延伸:时间复杂度和空间复杂度的概念

• 时间复杂度:执行算法所需要的计算工作量

  • 时间复杂度计算方式
  • O(n) --线性阶
    
  • O(1) -- 常数阶
    
  • O(n^2) -- 平方阶
    
• 常见的时间复杂度:常数阶,线性阶,平方阶,立方阶,对数阶,nlog2n阶,指数皆

• 空间复杂度:算法需要消耗的内存空间,记作S(n)=O(f(n))

  • 包括程序代码所占用的空间,输入数据所占用的空间和辅助变量所占用的空间这三方面空间
  • 空间复杂度计算方式(与时间复杂度类似)

  用空间换取时间

  • 冒泡排序的元素交换,空间(时间)复杂度O(1)

冒泡排序,直接插入排序,希尔排序,选择排序,快速排序,堆排序,归并排序

二分查找

时间复杂度:最差(O(log2n)),平均(O(log2n))
空间复杂度:迭代(O(1)),递归(O(log2n))

1,1,2,3,5,8,13,21,34...求第30位的数是多少,请用伪代码描述其实现方法

    $arr = [1,1];
    for ($i = 2; $i < 30; $i++) {
        $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
    }
    echo $arr[29];

写一个函数,实现以下功能:字符串"opend_door" 转换成 "OpenDoor","make_by_id" 转换成 "MakeByid"

function get_str ($str)
   {
           $arr = explode('_', $str);
           $new_str = '';
           for ($i = 0; $i < count($arr); $i++) {
               $new_str .= ucwords($arr[$i]);
        }
           
           return $new_str;
   }
    
   $str = 'open_door';
   
   echo get_str($str);

不适用PHP函数,用方法写一个反转字符串的函数

function get_str ($str)
   {
           $new_str = '';
           
           for ($j = 0; true; $j++) {
               if (!isset($str[$j])) {
                   break;
            }
        }
           
           for ($i = $j - 1; $i >= 0; $i--) {
               $new_str .= $str[$i];
        }
           
           return $new_str;
   }
   
   $str = 'abcdef';
   
   echo get_str($str);

不使用array_merge()完成多个数组的合并

function my_merge ()
    {
        $arr = func_get_args();
        
        $str = '';
        for ($i = 0; $i < count($arr); $i++) {
            if (!is_array($arr[$i])) return '参数错误';
            $str .= implode(',', $arr[$i]) . ',';
        }

        $str = trim($str, ',');
        $arr_tol = explode(',', $str);
        
        return $arr_tol;
    }
    
    $arr1 = [1,3];
    $arr2 = [6,4];
    
    echo '<pre>';
    var_dump(my_merge($arr1, $arr2));