为什么要研究算法，算法到底有什么用? 冒泡排序、插入排序、快速排序
什么是算法？算法是解决问题的操作步骤，算法每执行一步都有其确定性。
解决同一问题，有着不同的解决思路，思路不同，效率不同，空间复杂度也是不一样。
算法的概念：一个问题可以有多种算法，每种算法有不同过的效率
常见算法考点：
冒泡排序原理和实现
查找算法
一个算法有五个特征：有穷性 确切性 输入项 输出项 可行性
选择合适的算法和改进算法
执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n的函数
T(n)=O(f(n))
问题的规模n越大，算法执行的时间增长率越高。时间复杂度。
O(1) 常数阶
O(n) 线性阶
O(n^2)
请将一个url地址中的page去掉
$url=$_SERVER['REQUEST_URI'];
$params=parse_url($url);
P($params);
parse_str($params['query'],$http);
P($http);
unset($http['page']);
$new_query=http_build_query($http);
P($new_query);
P($params['path']."?".$new_query);
function P($_data){
echo "<pre style='color:blue'>";
print_r($_data);
echo "</pre>";
}
时间复杂度和空间复杂度
常见排序算法
常见查找算法
冒泡排序
两两相邻的数进行比较，如果反序就交换，否则不交换。
直接插入排序
希尔排序
选择排序
快速排序：快
堆排序
归并排序：那个算法 最快
请描述时间复杂度和空间复杂度的概念
一个有序数组中，查询特定item是否存在的最优算法是什么？时间复杂度是什么？
这个就是快速查找法 或归并排序法 二分查找法 log2n 速度最快
查找：
分两种查找方式 1、顺序查找 2、二分查找
二分查找的效率高于顺序查找， 前提，数据是顺序排序
二分查找时间复杂度最差是O(log2n) 对数阶，顺序查找的时间复杂度最差为O(n)，所以二分查找速度更快。
在递归情况下，二分查找法更消耗内存，空间复杂度是O(log2n)，迭代复杂度是O(1)
冒泡排序
$arr = array(10, 2, 36, 14, 25, 10,23, 85, 99, 45);
function bubbling($data){
$len=count($data);
for($i=1;$i<$len;$i++){
for($j=0;$j<$len-$i;$j++){
if($data[$j]>$data[$j+1]){
$temp=$data[$j];
$data[$j]=$data[$j+1];
$data[$j+1]=$temp;
}
}
}
return $data;
}
$data=bubbling($arr);
print_r($data);快速排序
时间复杂度：最差 O(n^2) 平均 O(nlog2n)
空间复杂度：最差 O(n) 平均 O(log2n)
快速排序、归并排序的理想时间复杂度是O(log2n)，但是快速排序的时间复杂度并不稳定，最坏情况下复杂度为O(n^2)，所以最理想的算法还是归并排序。
$arr = array(10, 2, 36, 14, 25, 10,23, 85, 99, 45);
function quickSort($data){
if(count($data)<=1)
return $data;
$first=$data[0];
$left=[];
$right=[];
$len=count($data);
for($i=1;$i<$len;$i++){
if($data[$i]<$first){
$left[]=$data[$i];
}else{
$right[]=$data[$i];
}
}
$left=quickSort($left);
$right=quickSort($right);
return array_merge($left,[$first],$right);
}
$data=quickSort($arr);
print_r($data);插入排序
时间复杂度：最差 O(n^2) 平均 O(n^2)
空间复杂度： O(1)
原理：每次从无序表中取出第一个元素，把它插入到有序表合适位置，使有序表仍然有序。
function insertSort($data){
$len=count($data);
for ($i=1;$i<$len;$i++) {
$j=$i;
while($j>0) {
if($data[$j-1]>$data[$j]){
$temp=$data[$j-1];
$data[$j-1]=$data[$j];
$data[$j]=$temp;
}
$j--;
}
}
return $data;
}
$data=insertSort($arr);
print_r($data);归并排序
$arr = array(10, 2, 36, 14, 25, 10,23, 85, 99, 45);
//merge函数将指定的两个有序数组(arr1,arr2)合并并且排序
//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据
function al_merge($arrA,$arrB){
$arrC = array();
while(count($arrA) && count($arrB)){
//这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,
//不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用
$arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB);
}
return array_merge($arrC, $arrA, $arrB);
}
//归并排序主程序
function al_merge_sort($arr){
$len = count($arr);
if($len <= 1)
return $arr;
//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组
$mid = intval($len/2);//取数组中间
$left_arr = array_slice($arr, 0, $mid);//拆分数组0-mid这部分给左边left_arr
$right_arr = array_slice($arr, $mid);//拆分数组mid-末尾这部分给右边right_arr
$left_arr = al_merge_sort($left_arr);//左边拆分完后开始递归合并往上走
$right_arr = al_merge_sort($right_arr);//右边拆分完毕开始递归往上走
$arr = al_merge($left_arr, $right_arr);//合并两个数组,继续递归
return $arr;
}
//$arr = array(12, 5, 4, 7, 8, 3, 4, 2, 6, 4, 9);
print_r(al_merge_sort($arr));header("Content-type:text/html;charset=utf-8");
$_data=array(1,5,2,6,7,3,9);
//请按照冒泡排序进行排序