本书涉及的数据结构有栈、队列、树、并查集、堆和图等；算法有各种排序、枚举、深度和广度优先搜索、图上的遍历，当然还有图论中不可缺少的四种最短路径算法、两种最小生成树算法、割点与割边算法、二分图的最大匹配算法等。
排序
桶排序
时间复杂度O(N+M)
冒泡排序
冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
从大到小排序。
冒泡排序的核心部分是双重嵌套循环。时间复杂度是O(N^2)。
快速排序
首先找一个数作为基准数，设置两个哨兵变量，指向序列最左边与最右边，找到右边小于基准数的数与左边大于基准数的数，两数交换，两哨兵变量相遇后，交换基准数与哨兵变量所指的数，然后对两哨兵变量左边与右边做相同的操作。
快速排序的每一轮处理其实就是将这一轮的基准数归为，直到所有的基准数都归为。
快速排序的最差时间复杂度和冒泡排序一样都是O(N^2),他的平均时间复杂度为O(NlogN)。
快速排序基于“二分”发。
排序算法还有选择排序、计数排序、基数排序、插入排序、归并排序、堆排序。堆排序是基于二叉树的排序。
栈、队列、链表
可使用两个数组模拟链表。第一个整数数组data是用来存放序列中的具体数字，另外一个整数数组right是用来存放当前序列中的每一个元素右边的元素在数组data中位置。
枚举
穷举法
万能的搜索
深度优先搜索
栈
广度优先搜索
队列
图的遍历
也是用深度或广度优先搜索
可使用二维数组来存储一个图。二维数组沿主对角线对称，说明是无向图。
广度优先搜索可找到两点之间经过最少点的路径。
最短路径
求有权图中两点最短路径，可使用深度优先搜索、广度优先搜索、Floyd、Bellman-Ford、Dijkstra等。
| Floyd | Dijkstra | Bellman-Ford | 队列优化的Bellman-Ford | |
|---|---|---|---|---|
| 空间复杂度 | O(N^2) | O(M) | O(M) | O(M) |
| 时间复杂度 | O(N^3) | O((M+N)logN) | O(NM) | 最坏是O(NM) |
| 适用情况 | 1.稠密图2.和顶点关系密切 | 1.稠密图2.和顶点关系密切 | 1.稀疏图2.和边关系密切 | 1.稀疏图2.和边关系密切 |
| 负权 | 可以解决负权 | 不能解决负权 | 可以解决负权 | 可以解决负权 |
注：其中N表示点数，M表示边数
Floyd算法虽然总体时间复杂度，但是可以解决负权边(不能解决负权环，实际上这几种都无法解决负权回路，因为一直循环下去总能找到更小的路径)，并且均摊到每一点对上，在所有的算法中还是比较好的. Floyd算法代码复杂度小也是一大优势. Dijkstra算法最大的弊端就是无法适应有负权边的图，但Dijkstra具有很好的可扩展性，另外在Dijkstra算法在选择剩余不在最短路径顶点的集合中选择最小值是可以堆优化，这样算法的时间复杂度可以达到O(MlogN). 当图中含有负边时，使用Bellman-Ford或者队列优化的Bellman-Ford算法.
Floyd-Warshall
每个定点都有可能使另外两个定点之间的路程变短。
核心代码：
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<.n;j++)
{
if(e[i][j]>e[i][k]+e[k][j])
{
e[i][j]=e[i][k]+e[k][j];
}
}
}
}
从i号顶点到j号顶点只经过前k号点的最短路径。(动态规划)
可求出任意两个点之间的最短路径。不能解决带有“负权回路”或者叫“负权环”，因为带有“负权回路”的图没有最短路径。
Dijkstra算法–单源最短路径
边数M少于N^2的叫稀疏图，M相对较大的为稠密图。
使用邻接表使时间复杂度优化到O(M+N)logN.
贪心策略的算法。
不能计算有负权边的图。
Bellman-Ford–解决负权边
for(k=1;k<=n-1;k++)
for(i=1;i<=m;i++
if(dis[v[i]]>dis[u[i]]+w[i])
dis[v[i]]-dis[u[i]]+w[i]
外循环n-1次（n为定点数），内循环数m次（m为边的个数）。dis数组存储源点到其他点的最短距离。u、v、w三个数组记录边的信息。例如第i条边存储在u[i]、v[i]和w[i]中，表示从顶点u[i]到顶点v[i]这条边（u[i]->v[i]）权值为w[i].
外循环n-1次，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。
如果在n-1轮松弛后最短路径仍然会发生变化，则该图必然存在负权回路。
优化
可以添加一个变量标记数组dis在本轮松弛中是否发生了变化，如果没有变化，则可以提前跳出循环。
每次仅对最短路径估计值发生变化了的顶点的所有出边执行松弛操作：Bellman-Ford队列优化
Bellman-Ford队列优化
队列广度优先搜索，
每次选取队首顶点u,对顶点u的所有出边进行松弛操作。例如有一条u->v的边,如果通过u->v这条边使得源点到顶点v的最短路程变短(dis[u]+e[u][v]<dis[v]),且顶点v不在当前的队列中,就将顶点v放入队尾。需要注意的是,同一个顶点同时在队列中出现多次是毫无意义的,所以我们需要一个数组来判重(判断哪些点已经在队列中)。在对顶点u的所有出边松弛完毕后,就将顶点u出队。接下来不断从队列中取出新的队首顶点再进行如上操作,直至队列空为止。
如果某个点进入队列的次数超过n次，则存在负环。
还有最短路径SPFA快速算法，也是基于队列优化的Bellman-Ford算法。
神奇的树
树其实就是不含回路的无向图
二叉树的特点是每个节点最多两个子节点。
如果二叉树中每个内部节点都有两个子节点，叫做满二叉树。深度为h且有2^h-1个节点。
完全二叉树：除h层外，其他层的节点个数达到最大数。
堆–神奇的优先队列
堆是一种特殊的特殊的完全二叉树
所有父节点都比子节点小，最小堆。反之，最大堆。
优先队列：支持插入元素和寻找最大（小）值元素的数据结构。
如果使用普通队列来实现这个两个功能，那么寻找最大元素需要枚举整个队列，这样的时间复杂度比较高。如果已排序好的数组，那么插入一个元素则需要移动很多元素，时间复杂度依旧很高。而堆就是一种优先队列的实现，可以很好的解决这两种操作。
堆还经常被用来求一个数列中第K大的数。只需要建立一个大小为K的最小堆，堆顶就是第K大的数。如果求一个数列中第K小的数，只最需要建立一个大小为K的最大堆，堆顶就是第K小的数，这种方法的时间复杂度是O(NlogK)。当然你也可以用堆来求前K大的数和前K小的数。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
堆排序的时间复杂度也是O(NlogN)与快速排序一样。
树还有很多神奇的用法：线段树、树状数组、Trie树（字典树）、二叉搜索树、红黑树（一种平衡二叉搜索树）。
更多精彩算法
1.最小生成树
Kruskal算法是一步步地将森林中的树进行合并，而Prim算法则是通过每次增加一条边来建立一棵树
Kruskal算法适用于稀疏图，没有使用堆优化的Prim算法适用于稠密图，使用了堆优化Prim算法则适用于稀疏图。
Kruskal算法：首先按照边的权值进行从小到大排序，每次从剩余的边中选择权值较小且边的二个顶点不在同一个集合内的边，加入到生成树种，直到加入了n-1条边为止。
时间复杂度：O(MlogM).
2.图的割点与割边
3.二分图最大匹配
增广路
还能更好吗——微软亚洲研究院面试
主元素问题
声明一个变量count = 0，声明一个常量size等于数组大小。
假设该数组的第一个元素a(1)为主元素，让其与a(2)进行比较，若相同，则使变量count+1，若不同，则count-1。然后继续比较a(3)。以此类推。
当与a(n)比较后，count = -1时，将count重新归为0，并重新假设a(n+1)为主元素，并继续与a(n+2)作比较。
当count>=(size-m)/2时，此时假设的主元素a(m)即为实际的主元素。
或遍历完整个数组后，当前假设的主元素为实际主元素。
book
- 艾伦·图灵传：如谜的解密者
- 图灵的秘密
- 编程之美
- 算法导论
- 思考的乐趣
- 数学之美
- 具体数学
- 算法帝国
