这几天断断续续看完了《啊哈！算法》，做点小复笔记
冒泡排序：比较相邻的元素，如果顺序不一样就将他们调换顺序，直到完成排序
快速排序：选择基准数，头尾指针往中间靠拢，如果两个指针指向的数字与基准数的比较有问题，则将其交换（跳跃式的交换）。然后再通过二分的思想递归进行这样的步骤，直到排序完成。
栈：先进后出
队列：先进先出
链表：方便插入、删除节点
深度优先搜索：关键在于解决当前该如何做，如果当前有没有被访问过的点，则访问该点，递归进行此步骤。若没有需要访问的点，则回到上一个点访问下一个点。直到所有点都被访问。
广度优先搜索：访问当前点的所有相邻的点（加入队列），将他们加入队列,然后再递归进行此操作，直到完成所有点。
图遍历中，广度优先搜索更加适用于所有边权值相同的情况。
图的邻接矩阵表示法：使用二维数组来储存图。
Floyd-Warshall：每个顶点有可能使另外两个定点之间的路程变短。
每经过一个点，更新数组中的距离。
Dijkstra（单源最短路）：
从选中的点开始，选出离当前点最近的点，对最近点的所有出边进行“松弛”（与现有的距离进行比较，如果比现有的距离小则更新距离）。
可以使用邻接表进行优化（当边数M远小于点数N的平方时）
树：不包含回路的连同无向图
n个结点有n-1条边，任意两点有且只有一条路径联通。
二叉树：每个节点最多有两个子节点。
满二叉树：所有的叶节点都有同样的深度，深度为h且有2的h次方-1个节点
完全二叉树：高度为h的二叉树，第h层从右向左连续缺若干节点。父节点编号为k，左子节点为2k，右为2k+1。子节点编号为x（无论左右），父节点为x／2（取整）。
堆：所有父节点都比子节点大或者小的完全二叉树。
***插入、删除节点的步骤
并查集（不相交集数据结构）：靠左+擒贼先擒王原则，将孤立的点合并为树。
网友评论