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));