数组 array
读取：1步到位，跳到内存地址 O(1)
查找：线性查找，最多N次
插入：最低效(插入在开头),N+1步，最高效(末尾),1步
删除： 最低效(删除第一项)，N步，最高效(末尾),1步
集合 set
不允许元素重复(基于数组)
读取：1步到位，跳到内存地址
查找：线性查找，最多N次
插入：插入前要查找，最低效(插入在开头),2N+1步，最高效(末尾),N+1步
删除： 最低效(删除第一项)，N步，最高效(末尾),1步
有序数组 sorted array
线性查找：查找一般快于无序数组
二分查找： 100最多7步，线性100步
O算法复杂度
O(1) < O(logN) < O(N) < O(NlogN) < O(N^2)< O(N^3)<O(2 ^N) < O(n!) < O(n^n)
忽略常数，区分不同算法长期增长率(存在一临界点)
只保留最高阶N
常数时间： O(1) 不局限于1步 读取
线性时间：O(N) 线性查找
对数时间：O(logN) 数据量翻倍，步数+1 二分法
二次时间：O(N^2) 嵌套循环， 冒泡排序，选择排序，插入排序
冒泡排序：比较+交换(相邻交换) O(N^2)
比较次数是 (N-1)+(N-2)+......+1，交换最坏和比较次数相同，总数为N(N-1)
选择排序(最小值 时变量与左侧比较) O((N^2)+N)
移除(N-1)+比较(N-1)+....+1+平移(N-1)+....+1+插入(N-1)= N^2+2N-2
插入排序在不同场景差异很大 最坏N^2 平均(N^2)/2 最好N
找两数组交集(比较+插入) 相互比较，相同值插入result
有break没交集N^2次比较 完全一样N次，不然无论什么情况都是N^2步
散列表 hash table O(1)
计算BAD=2 * 1 * 4=8，返回第8个格子
每次对同一串字符调用该散列函数，返回同一数字串
如果放入格子，冲突，分离链接(格子里放一个数组)，若hash table含有array，线性查找，步数最多O(N)
hash table效率（避免冲突，节约空间）
要存多少数据
有多少可用格子
用什么样的散列函数
最理想的负载因子=0.7 (每增加7个元素，增加10个格子)
投票：投票保存(插入末尾)+点票(循环遍历)
array需要O(1)+O(N) hash table需要 O(1)投票时已经在计数(点票)
Stack栈 Queue队列
Stack：处理临时数据
(存储数据方式和Array相同，把元素排成一行， 类似盘子堆叠)
只能 在末尾(栈顶) 插入数据
只能在 读取/移除 末尾数据
Queue：打字机作业设置，后台任务等
FIFO，先进先出
只能 在末尾插入数据
只能 读取/移除 开头数据
递归 recursion
几乎左右循环都可以转换成递归
递归可自然应用于需要重复自身的算法，增加代码可读性
适用于无法预估计算深度的问题
(遍历文件)
快速排序 O(NlogN) 最坏情况O(N^2)
最佳情况：每次分区后，轴都落在子数组中间 严重依赖于分区
分区操作：比较+交换 O(N)
一次分区至少N次比较，交换取决于排列情况，最少1，最多N/2次
随机排列为N/4，+N 是1.25N
一个无序数组，不需要排序，只要找出第10小，或第5大的值，如同找出第25%：
排序+查找—：即使用快速排序，也要O(NlogN)
快速选择
对数组分区（快排+二分查找结合）不需要把整个数组排序
平均O(N) N个元素，2N步
链表[Linked List]：
结点(node)：组成链表不连续的格子，可分布在内存各个地方
每个node除了保留数据，还保留写一个node的内存地址，用来指示下一node内存地址的额外数据成为链Link
每个node需要两个格子，一个数据存储，一个list，最后一个node的list是null,使用LinkList只需要知道第一个node在内存的位置
读取 最坏情况最后一个引索 O( N)
查找 最坏情况最后一个格子 O(N)
插入 插入表头只要1步，但插入前要找到引索(即读取) O(N)
删除 效率和插入相似
亮点：高效的遍历单个列表并删除其中多个元素
每读取一个地址，用正则表达式验证其有效性，如果发现无效，则删除
数组每次删除需要 遍历N步，每次删除需要右移O(N) n个错，需要N+nN
链表每次删除只要1步， 总共N+n步
双向链表
数组作为queue底层：末尾插入O(1)，开头删除O(N)
链表作为queue底层：末未插入O(N)，开头删除O(1)
双向链表作为queue底层：插入和删除都为O(1)，能直接访问前端末端节点
二叉树
子节点个数：0,1,2 两个子节点，大于父节点在右，小于的在左
查找：O(logN) 和数组二分查找一样
插入：O(logN) 查找+插入1步 有序数组是O(N)
只有随意打乱数据才平衡，插入的都是已排序数据，tree失去平衡，低效 完全失衡二叉树查找是O(N)
删除：O(logN) 要删除的节点没有子节点，直接删掉；有一个节点，将子节点填到被删除节点位置上；有两个节点，则替换为后继节点(右子节点中最小的)
实例：书目维护，经常变动，不适合有序数组，使用二叉树。书名搜索和更新，可用二叉树查找、插入和删除 访问数据中所有元素：遍历数组
中序遍历：递归 遍历效率O(N)
强大的基于节点的数据结构，即能维持顺序，又能快速查找、插入和删除
图
散列表（hash table）
广度优先搜索(使用queue) O(V+E) V个顶点，每个顶点出一次queue，E条边，每条边用两次，访问两端顶点，2E次访问邻接点
关系型数据， M个朋友，需要O(MlogN)次查询，一张user信息表，一张关系表(id代指用11户)，id一般有序，二分查找是O(logN).
图数 据库，定位到user，M次即可(遍历连接的边)
Dijkatra算法，确定最短路线(总价最低航线)