因为之前的笔记和书籍相关知识都是零零散散的， 没有一个汇总， 所以写了这篇博客。有些算法很简单，复杂度一眼都能看得出来， 几乎不需要记忆 ， 但是有些算法或者数据结构的操作的复杂度就不是一眼可以看得出来， 推导也是很费时间的， 所谓常识就是应该熟记于心且被认可的知识。
必须掌握的知识
- DataStructure
- 链表
- 二叉树
- 二叉搜索树
- 栈
- 队列
- 散列表
- 算法
- 二分查找
- 快速排序
- 归并排序
- 堆排序
- 插入排序
- 树的插入/查找/删除
- 广度优先搜索
- 深度优先搜索
该注意的点
- 实用的排序算法有四种：插入、快速、归并、堆。其余的都不值得深究。这几个排序算法都有其特点，涵盖了常见的使用场景，在其特定的使用场景下是效率最高的。
- 插入排序 : 在小数据量或者数据都较为有序的时候比起归并和快速排序有更佳的时间效率, 插入排序在这种情况下，只需要从头到尾扫描一遍，交换、移动少数元素即可；时间复杂度近乎 o(N)))。
- 快速排序 : 时间复杂度依赖数据打乱的程度
- 快排最差情形的时间复杂度是O(n2), 平均是O(nlogn)
- 就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
- 最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
- 最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
- 选择基准的方式决定了两个分割后两个子序列的长度，进而对整个算法的效率产生决定性影响, 比如当如果一个有序递增序列, 每次选基准都选最后一个, 那肯定效率 很差了啊
- 归并排序 : 时间复杂度稳定但是占用2N的内存
- 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)
- 还有一种空间复杂度为O(1)的归并排序的实现
- 堆排序 : 在不能一次排序N个数据并要求选出前M个数据时使用。
- 插入排序、堆排序、快速排序等都是原址排序。归并排序是非原址的。
- 插入排序、归并排序是稳定的, 堆排序、快速排序是不稳定的。
- 内省排序: std的sort就是用的内省排序. 此算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值即logN）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持o(NlogN)的时间复杂度。
为什么在平均情况下快速排序比堆排序要优秀
堆排序是渐进最优的比较排序算法，达到了O(nlgn)这一下界，而快排有一定的可能性会产生最坏划分，时间复杂度可能为O(n^2)，那为什么快排在实际使用中通常优于堆排序？
- 虽然quick_sort会n^2（其实有稳定的nlgn的版本），但这毕竟很少出现。heap_sort大多数情况下比较次数都多于quick_sort，尽管大家都是nlgn。那就让倒霉蛋倒霉好了，大多数情况下快才是硬道理。
- 堆排比较的几乎都不是相邻元素，对cache极不友好，这才是很少被采用的原因。数学上的时间复杂度不代表实际运行时的情况.快排是分而治之，每次都在同一小段进行比较，最后越来约接近局部性。反观堆排，堆化过程中需要一直拿index的当前元素A和处于index*2 + 1 的子元素B比较, 两个元素距离较远。(局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。)
如何解决快排和堆排都不够好的问题?
使用 内省排序 , std的sort就是用的内省排序.
各类算法的复杂度汇总表
算法与数据结构-综合提-C++版
- 第一章：当我们在讨论算法的时候，我们在讨论什么？
1-1 我们究竟为什么要学习算法
1-2 课程介绍 - 第二章：排序基础
2-1 选择排序法
2-2 使用模板（泛型）编写算法
2-3 随机生成算法测试用例
2-4 测试算法的性能
2-5 插入排序法
2-6 插入排序法的改进
2-7 更多关于O（n*2）排序算法的思考 - 第三章：高级排序问题
3-1 归并排序法
3-2 归并排序法的实现
3-3 归并排序法的优化
3-4 自底向上的归并排序算法
3-5 快速排序法
3-6 随机化快速排序法
3-7 双路快速排序法
3-8 三路快速排序法
3-9 归并排序和快速排序的衍生问题 - 第四章：堆和堆排序
4-1 为什么使用堆
4-2 堆的基本存储
4-3 Shift Up
4-4 Shift Down
4-5 基础堆排序和Heapify
4-6 优化的堆排序
4-7 排序算法总结
4-8 索引堆
4-9 索引堆的优化
4-10 和堆相关的其他问题 - 第五章：二分搜索树
5-1 二分查找法
5-2 二分搜索树基础
5-3 二分搜索树的节点插入
5-4 二分搜索书的查找
5-5 二分搜索树的遍历（深度优先遍历）
5-6 层序遍历（广度优先遍历）
5-7 删除最大值，最小值
5-8 二分搜索树的删除
5-9 二分搜索树的顺序性
5-10 二分搜索树的局限性
5-11 树形问题和更多树。 - 第六章：并查集
6-1 并查集基础
6-2 Qucik Find
6-3 Quick Union
6-4 基于size的优化
6-5 基于rank的优化
6-6 路径压缩 - 第七章：图论
7-1 图论基础
7-2 图的表示
7-3 相邻点迭代器
7-4 图的算法框架
7-5 深度优先遍历和连通分量
7-6 寻路
7-7 广度优先遍历和最短路径
7-8 迷宫生成，ps抠图–更多无权图的应用 - 第八章：最小生成树
8-1 有权图
8-2 最小生成树问题和切分定理
8-3 Prim算法的第一个实现
8-4 Prim算法的优化
8-5 优化后的Prim算法的实现
8-6 Krusk算法
8-7 最小生成树算法的思考 - 第九章：最短路径
9-1 最短路径问题和松弛操作
9-2 Dijkstra算法的思想
9-3 实现Dijkstra算法
9-4 负权边和Bellman-Ford算法
9-5 实现Bellman-Ford算法
9-6 更多和最短路径相关的思考 - 第十章：结束语
10-1 总结，算法思想，大家加油！
玩转算法面试_从真题到思维全面提升算法思维
第1章 算法面试到底是什么鬼?
一提起算法面试，很多同学就会心有余悸。可其实，大多数企业的算法面试，并没有那么可怕。并不是一定要啃完整本《算法导论》，才能玩儿转算法面试；也并不是只有ACM参赛选手，才能笑傲算法面试。恰恰相反，大多数算法面试关注的算法思维，其实很基础。在这一章，和大家聊一聊，算法面试，到底是什么鬼？…1-1 算法面试不仅仅是正确的回答问题试看
1-2 算法面试只是面试的一部分试看
1-3 如何准备算法面试试看
1-4 如何回答算法面试问题第2章 面试中的复杂度分析
很多同学一提起复杂度分析就头疼，马上想起了《算法导论》中复杂的数学推导。但其实在一般的企业面试中，对复杂度的分析要求并没有那么高，但也是绕不过去的坎儿。在这一章，和大家介绍一下，面试中需要掌握的复杂度分析。…2-1 究竟什么是大O（Big O）
2-2 对数据规模有一个概念
2-3 简单的复杂度分析
2-4 亲自试验自己算法的时间复杂度
2-5 递归算法的复杂度分析
2-6 均摊时间复杂度分析（Amortized Time Analysis）
2-7 避免复杂度的震荡第3章 数组中的问题其实最常见
面试中的算法问题，有很多并不需要复杂的数据结构支撑。就是用数组，就能考察出很多东西了。其实，经典的排序问题，二分搜索等等问题，就是在数组这种最基础的结构中处理问题的。在这一章中，我们学习常见的数组中处理问题的方法。…3-1 从二分查找法看如何写出正确的程序
3-2 改变变量定义，依然可以写出正确的算法3-3 在LeetCode上解决第一个问题 Move Zeros
3-4 即使简单的问题，也有很多优化的思路
3-5 三路快排partition思路的应用 Sort Color
3-6 对撞指针 Two Sum II - Input Array is Sorted
3-7 滑动窗口 Minimum Size Subarray Sum
3-8 在滑动窗口中做记录 Longest Substring Without Repeating Characters第4章 查找表相关问题
查找，是使用计算机处理问题时的一个最基本的任务，因此也是面试中非常常见的一类问题。很多算法问题的本质，就是要能够高效查找。学会使用系统库中的map和set，就已经成功了一半。4-1 set的使用 Intersection of Two Arrays
4-2 map的使用 Intersection of Two Arrays II
4-3 set和map不同底层实现的区别
4-4 使用查找表的经典问题 Two Sum
4-5 灵活选择键值 4Sum II
4-6 灵活选择键值 Number of Boomerangs
4-7 查找表和滑动窗口 Contain Duplicate II
4-8 二分搜索树底层实现的顺序性 Contain Duplicate III第5章 在链表中穿针引线
链表是一种特殊的线性结构，由于不能像数组一样进行随机的访问，所以和链表相关的问题有他自身的特点。我将之称为穿针引线。我们在这一章，就来看一看，如何在链表中穿针引线。5-1 链表，在节点间穿针引线 Reverse Linked List
5-2 测试你的链表程序
5-3 设立链表的虚拟头结点 Remove Linked List Elements
5-4 复杂的穿针引线 Swap Nodes in Pairs
5-5 不仅仅是穿针引线 Delete Node in a Linked List
5-6 链表与双指针 Remove Nth Node Form End of List第6章 栈，队列，优先队列
栈和队列虽然是简单的数据结构，但是使用这些简单的数据结构所解决的算法问题不一定简单。在这一章里，我们将来探索，和栈与队列相关的算法问题。6-1 栈的基础应用 Valid Parentheses
6-2 栈和递归的紧密关系 Binary Tree Preorder, Inorder and Postorder Traversal
6-3 运用栈模拟递归
6-4 队列的典型应用 Binary Tree Level Order Traversal
6-5 BFS和图的最短路径 Perfect Squares
6-6 优先队列
6-7 优先队列相关的算法问题 Top K Frequent Elements第7章 二叉树和递归
递归，是使用计算机解决问题的一种重要的思考方式。而二叉树由于其天然的递归结构，使得基于二叉树的算法，均拥有着递归性质。使用二叉树，是研究学习递归算法的最佳入门方式。在这一章里，我们就来看一看二叉树中的递归算法。…7-1 二叉树天然的递归结构, 104, 111, 100, 101, 222, 110
7-2 一个简单的二叉树问题引发的血案 Invert Binary Tree
7-3 注意递归的终止条件 Path Sum, 112, 111, 404
7-4 定义递归问题 Binary Tree Path, 257, 113, 129
7-5 稍复杂的递归逻辑 Path Sum III, 437
7-6 二分搜索树中的问题 Lowest Common Ancestor of a Binary Search Tree, 235, 98, 450, 108, 230, 236第8章 递归和回溯法
回溯法是解决很多算法问题的常见思想，甚至可以说是传统人工智能的基础方法。其本质依然是使用递归的方法在树形空间中寻找解。在这一章，我们来具体看一下将递归这种技术使用在非二叉树的结构中，从而认识回溯这一基础算法思想。…8-1 树形问题 Letter Combinations of a Phone Number
8-2 什么是回溯, 93, 131
8-3 排列问题 Permutations, 47
8-4 组合问题 Combinations, 77, 39, 40, 216, 78, 90, 401
8-5 回溯法解决组合问题的优化
8-6 二维平面上的回溯法 Word Search, 79
8-7 floodfill算法，一类经典问题 Number of Islands-
8-8 回溯法是经典人工智能的基础 N Queens第9章 动态规划基础
很多同学听到“动态规划”的名称可能会望而生畏，觉得动态规划的问题都很复杂。但其实，动态规划本质依然是递归算法，只不过是满足特定条件的递归算法。在这一章里，我们就来逐步解开动态规划的神秘面纱9-1 什么是动态规划
9-2 第一个动态规划问题 Climbing Stairs, 70, 120, 64
9-3 发现重叠子问题 Integer Break, 343, 279, 91, 62, 63
9-4 状态的定义和状态转移 House Robber, 198, 213, 337, 309,
9-5 0-1背包问题
9-6 0-1背包问题的优化和变种
9-7 面试中的0-1背包问题 Partition Equal Subset Sum, 416, 322, 377, 474, 139, 494
9-8 LIS问题 Longest Increasing Subsequence
9-9 LCS，最短路，求动态规划的具体解以及更多第10章 贪心算法
通常同学们可能会认为贪心算法比较简单。确实，通常贪心算法的实现非常容易，但是，一个问题是否能够使用贪心算法，是一定要小心的。我们在这一章来看一看，贪心算法可能会有哪些坑。10-1 贪心基础 Assign Cookies, 455, 392
10-2 贪心算法与动态规划的关系 Non-overlapping Intervals, 435
10-3 贪心选择性质的证明第11章 课程结语
看完整个课程，我不能保证所有的同学都能百分百地对每一个算法面试问题应答自如，但认真学习的同学对大部分问题都应该已经有了一个合理的思维路径。在最后一章，我们再来简单地总结一下，并祝每一位同学都能找到自己喜欢的工作，大展宏图：）…11-1 结语