PPT1

考点：

概念：

伪代码：

• 就像华容道，始终空一格，由于Key已经拿了出来，不用担心右边被左边覆盖，所以比它大就往右挪，直到不大于Key，就把Key填到格子里。
• 这里是>，但有的是>=（不是≥）

帮助理解：

PPT2

考点：

概念：

伪代码：

• if p < r，很多算法都有这个前提

• 没有写函数体，直接写了函数名字，最后还要加上一个return。

• for j=p to r-1 exchange…with…

• for…to return 等等，没有括号

• 注意是lgn不是logn

• 除了用一个A[随机数]交换了A[r]再分解，其他的地方都一样

• i与它的左右子树相比较，在三者不大于heapsize的基本前提下，如果A[i]不是最大的那个，就和A[largest]互换。注意lc,rc,i,largest都是序号。

• 上图是维护最大堆的T(n)。

帮助理解：

• r的位置不能预先确定，i来划分两个分区，j来遍历每个数，如果A[j]比4小，就把i右边的大数和a[j]互换，相当于变相增加了小数区间，大数区间整体右移。直到j=r-1.然后把r和i右边（i+1)换个位置，插入进去就好了。

• 先乱序堆，然后堆排序。大根堆和最小值交换，最大值回到数组，堆排序再次得到大根堆，此时大根堆是第二大值，再交换，以此类推。

递归式求解——代入法、递归树与主定理 - 知乎 (zhihu.com)

1.6 快速排序 | 菜鸟教程 (runoob.com)

(12条消息) 什么是二叉堆？_stay hungry ! stay foolish!-CSDN博客_二叉堆

[图解] 快速排序 - 简书 (jianshu.com)

PPT3

考点：

概念：

伪代码

• length(s) si>=fj A U {i} j <- i

• 此时已经有了具体的乱序

• 别忘了rank[x]++ rank是深度

• G是图，W是权重，U和V是边

理解记忆：

• 查询是int，其他是union

贪心算法：贪心选择性与优化子结构 (itxueyuan.com)

(6条消息) 哈夫曼编码（最优前缀码）_Debuging-CSDN博客

(6条消息) 算法导论–最小生成树（Kruskal和Prim算法）_勿在浮砂筑高台-CSDN博客_prim算法

傻子都能看懂的并查集入门 - SegmentFault 思否

(6条消息) 分治法，动态规划及贪心算法区别_longwufengfei的专栏-CSDN博客

PPT4

考点：

概念：

伪代码

帮助理解：

(6条消息) 分治法，动态规划及贪心算法区别_longwufengfei的专栏-CSDN博客

(6条消息) 动态规划 最长公共子序列 过程图解_hrn1216的博客-CSDN博客_最长公共子序列

算法设计与分析——矩阵连乘问题（动态规划） - 王陸 - 博客园 (cnblogs.com)