常见算法
逻辑思维
对于无序数组排序，最优的时间复杂度是什么
归并排序 ，用php写出一个实际的例子
一个有序数组中，查询特定item是否存在的最优算法是什么，时间复杂度是什么
二分查找法 o(log2n)
请写出常见的排序算法，并用php实现冒泡排序，将数组按照 从小到大的方式进行排序
那个算法最快
归并排序 快速排序 同样快 但是 快速排序不稳定 归并排序是理想算法
冒泡排序原理和实现
算法的概念
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令 表示一个或多个操作
一个问题可以有多重算法，每种算法都有不同效率
一个算法具有五个特征:
有穷性 可以计算完不然是死循环
确切性 每一步都要有意义
输入项 1+100
输出项 有结果
可行性 每一步都是正确的
1+2+3+n n(n+1)/2(Sn=(a1+an)*n*d/2,d是公差（相邻2数之间的差），a1是首项，an是末项，n是项数.这是个等差数列.)
时间复杂度和空间复杂度的概念
算法评定
算法分析的目的在于选择合适算法和改进算法
一个算法的评价主要从时间复杂度和空间复杂度来考虑
时间复杂度
执行算法所需要的计算工作量，一般来说，计算机算法是问题规模n的函数f(n)，算法的时间复杂度也因此记做 T(n)=O(f(n))
问题的规模n越大，算法执行的时间的增长率与 f(n)的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）
时间复杂度计算方式
得出算法计算次数公式
用常数1来取代所有时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶存在且不是1，则去除与这个项相乘的常数
平（立方阶 ）o(n^2) 双/三重循环 在修改后的运行次数函数中，只保留最高阶项 如果最高阶存在且不是1，则去除与这个项相乘的常数 如 是 n^2+n+1 只保留最高阶层
线性阶 o(1) 只要次数是常数都用1来替代 o(1) 用常数1来取代所有时间中的所有加法常数
常数阶 o(n) 计算次数 如 1+2+3+n 得出算法计算次数公式
对数阶 o(log2n)
while($n>=1){
$n=$n/2;
}
n/(2^m)=1
2^m=n
m=log2n
O(2^n)
20 n
10 n/2
5 n/2/2
2.5 n/2/2/2
1 n/2/2/....
效率 O(1)>O(log2n)>O(n)>O(nlog2n)>O(n^2)>O(n^3)>O(2^n)>O(n!)>O(n^n)
最坏情况，最坏情况时的运行时间，一种保证，如果没有特别说明，说的时间复杂度即为最坏的时间复杂度
平均情况，期望运行的时间
空间复杂度
算法需要消耗的内存空间，记做 S(n)=o(fn)
包括程序代码所占用的空间，输入数据所占用的空间和辅助变量所占用的空间这三个方面
计算和表示方法与时间复杂度类似，一般用复杂度的渐进性来表示
有时用空间换区时间
冒泡排序的元素交换 空间复杂度O(1)--只会有一个临时变量
常见的排序算法
冒泡排序
原理:两两相邻的数进行比较，如果反序就交换，否则就不交换
时间复杂度 最坏 O(n^2) 平均 O(n^2)
空间复杂度 O(1)
//冒泡排序
$arr=array(8,2,11,1);
for($i=0,$c=count($arr);$i<=$c;$i++){
for($j=0;$j<$c-1;$j++){
if($arr[$j]>$arr[$j+1]){//判断数组大小，颠倒位置
$temp=$arr[$j+1];
$arr[$j+1]=$arr[$j];
$arr[$j]=$temp;
}
}
}
dump($arr);
直接插入排序
原理:每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序
时间复杂度 最坏 O(n^2) 平均 O(n^2)
空间复杂度 O(1)
希尔排序
原理:将待排序的数据根据增量分成几个子序列，对子序列进行插入排序，知道增量为1.直接进行插入排序，增量的排序，一般是数组的长度的一般，再变为原来增量的一般，知道增量为1
时间复杂度 最坏 O(n^2) 平均O(n*log2n)
空间复杂度 O(1)
选择排序
原理：每次从待排序的数组元素中选出最小(或最大)的一个元素，存放在序列的起始位置，知道全部待排序的数据元素排完
时间复杂度 最坏 O(n^2) 平均 O(n^2)
空间复杂度 O(1)
快速排序
原理 ；通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归完成
时间复杂度 最坏 O(n^2) 平均O(n*log2n)
空间复杂度 O(n) 平均O(log2n)
堆排序
原理 把待排序的元素按照大小在二叉树位置上排列，排序好的元素要满足，父节点的元素要大于等于子节点，这个过程就做对话过程，如果分界点存放的是最大的数，则叫做大根堆，如果是最小，就叫小根堆，可以把根节点拿出来，然后再堆化，循环到最后一个节点
时间复杂度 最坏 O(nlog2n)平均O(nlog2n)
空间复杂度 O(1)
归并排序(最理想算法)V -》快速排序V
原理:将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列 再把有序的子序列合并为整体有序序列
时间复杂度 最坏 O(nlog2n)平均O(nlog2n)
空间复杂度 O(n)
常见的查找算法
二分查找
原理:从数组的中间元素开始，如果中间元素正好是要查找的元素，搜索结束，如果某一个特定元素大于或者小于中间元素，则在数组大于或者小于中间元素的那一半中查找 而且跟开始一样从中间开始比较 如果某一步骤数组为空 代表找不到
时间复杂度 最坏 O(log2n)平均O(log2n)
空间复杂度 迭代O(1) 递归o(log2n)
顺序查找
按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止
时间复杂度 最坏 O(n)平均O(n)
空间复杂度 O(1)
总结，二分查找算法的时间复杂度最差是O(log2n),顺序查找的时间复杂度最差为o(n),所以二分查找法更快，但是递归情况下，二分查找法更消耗内容，时间复杂度为O(log2n)
