《数据结构与算法图解》 杰伊·温格罗

数组 链表 栈 队列 哈希表 二叉树

链表是一种线性表  节点  数据域 指针域

栈 先进后出   栈底，栈顶   压入  弹出

队列   
先进先出（First in First out） ，队尾插入元素叫做入队，对头删除元素叫做出队

哈希表 Hash表 散列表  键值对 


二叉树   左子树（left subtree） 右子树（right subtree）
二叉查找树

有序树
各个节点的度不能超过 2，只能有 0 1 2 个子节点

满二叉树
树高度为h，由2^h-1个节点构成



算法分析
大O符号
时间复杂度  空间复杂度 Space complexity
算法的步数
算法需要的额外空间

常见的时间复杂度
常数阶O(1)
线性阶O(n)
平方阶O(n²)
对数阶O(logn)
线性对数阶O(nlogn)



经典算法
递归算法 贪心算法 分治算法 动态规划算法 贪婪算法 回溯算法


递归算法 自己调用自己，一个方法在执行过程中调用自身, 就称为 “递归”。

func( mode){
if(endCondition){      //递归出口
end;
}else{
func(mode_small)  //调用本身，递归
}
}
 

贪心算法，又名贪婪算法，是指在对问题求解时，总是做出在当前看来是最好的选择，从而希望能够导致结果是最好或者最优的算法。

 

分治算法，分而治之，把一个复杂的问题分成两个或更多的相同或相似的子问题，
再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解。

 
动态规划，Dynamic Programming，把原问题分解为相对简单的子问题以求解的方法

每次决策依赖于当前状态，个决策序列就是在变化的状态中产生出来的，
这种多阶段最优化决策解决问题的过程就称为动态规划。

 
贪婪算法，Greedy Algorithm，又名贪心算法 
所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

 
回溯算法，是一种选优搜索法，又称为试探法，按选优条件向前搜索以达到目标。
当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择
 
分支限界法算法




经典排序
插入排序  冒泡排序 快速排序 选择排序 希尔排序 堆排序 


插入排序，InsertionSort，直接插入排序
每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中，直到全部记录插入完成为止。


冒泡排序，Bubble Sort
每一个元素像小气泡一样，根据自身大小一点一点向数组的一侧移动
两两比较，小的上浮，大的下沉


快速排序, Quick Sort，由C.A.R Hoarse 在1960年提出

快速排序 从冒泡排序 算法演变而来，是对冒泡排序 的一种改进
因元素之间的比较次数较少，速度较快，因而得名

 
选择排序，Select Sort

 

希尔排序，Shell ’s Sort，是插入排序 的一种
希尔（Donald Shell）于1959年提出
也称递减增量排序算法，是插入排序改进版本


堆排序，Heap Sort，将数据看成近似完全二叉树结构，并根据完全二叉树的特性进行排序





经典查找算法
顺序查找、二分查找、二叉排序树查找