数据结构

• 常见数据结构

Array 数组是 最简单 而且 应用最广泛 的数据结构

特征：1、使用连续内存空间来存储2、存放相同类型或着衍生类型的元素（PHP数组比较特别，可以存放八种数据类型）3、通过下标来访问

Set 集合

特征：1、保存不重复的元素

Map 字典

特征：1、就是PHP关联数组，以Key/Value形式存储

Stack 栈，与队列相似

特征：1、存储数据是先进先出，栈只有一个出口，只能从栈顶部添加和删除元素

Heap 堆，与二叉树的数据结构相似

特性：1、子节点的键值和索引总小于他的父节点

list 线性表，由零个或多个数据元素组成的有序序列

特性：1、线性表是一个序列，在PHP中就是索引数组

Queue 队列

特性：1、先进先出，并发中使用，可以安全地将对象从一个任务传给另一个任务，可以使用PHP数组模拟

• 如何模拟双向链表？

使用数组Array来实现array_shift() / array_unshift()array_pop() / array_push()

其它逻辑算法

• 重点：找出算法的规律，再用代码来实现

模拟PHP内置函数来实现某些功能

不使用PHP内置函数的前提下，实现字符串翻转

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

常见算法考点

• 算法是什么？

是一种解决问题的计算方法，一个问题有多种算法来解决，每种算法效率都不同，根据需求选择最优算法

• 时间复杂度和空间复杂度

作用：用于 评定 某算法 是否合适？是否高效？

时间复杂度：执行算法所需要的时间

空间复杂度：执行算法所需要的内存空间

常见时间复杂度 例如：常数阶O(1)、线性阶O(n)、平方阶O(n^2)、立方阶O(n^3)、对数阶O(log2n)、nlog2n阶O(nlog2n)、指数阶O(n^n)效率从大到小：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)时间复杂度计算方式：得出算法的计算次数（空间复杂度与之类似）用1来取代说有确定次数的加法

• 常见排序算法

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

冒泡排序               最坏情况        平均情况时间复杂度      O(n^2)         O(n^2)空间复杂度      O(1)直接插入排序               最坏情况        平均情况时间复杂度      O(n^2)         O(n^2)空间复杂度      O(1)希尔排序               最坏情况        平均情况时间复杂度      O(n^2)         O(nlog2n)空间复杂度      O(1)选择排序               最坏情况        平均情况时间复杂度      O(n^2)         O(n^2)空间复杂度      O(1)快速排序               最坏情况        平均情况时间复杂度      O(n^2)         O(nlog2n)空间复杂度      O(n)           O(log2n)归并排序               最坏情况        平均情况时间复杂度      O(nlog2n)         O(nlog2n)空间复杂度      O(n)堆排序               最坏情况        平均情况时间复杂度      O(nlog2n)      O(nlog2n)空间复杂度      O(1)

• 常见查找算法

二分查找、顺序查找

二分查找        最坏情况        平均情况时间复杂度      O(log2n)       O(log2n)空间复杂度      迭代O(1)       递归O(log2n)顺序查找        最坏情况        平均情况时间复杂度      O(n)           O(n)空间复杂度      O(1)