Book Notes · Sedgewick · Algorithms 4e

算法
实现对照

按四大主题读：基础、排序、查找、图；字符串只作概览。配套站点可查可视化，机制对错仍以全书为准。

01基础

背包、队列、栈先当 ADT：规定对象、关系和操作，不规定数组还是链表。

ADT→数组 / 链表→操作代价不同

下标访问只有顺序存储是 O(1)。单链表按位定位 O(n)；已有前驱后改链才 O(1)。循环队列要先声明空满约定。

选择、插入、希尔、归并、快排、优先队列（堆）是这本书的主干。本站演示用同一数组对照冒泡、直接插入、简单选择、Lomuto 快排。

冒泡在「相等不换」的标准实现下稳定。直接插入稳定；希尔是插入思想但不稳定。快排在输入排列等概率/随机输入假设下平均 O(n log n)，最坏 Θ(n²)。建堆 O(n)，不是 O(n log n)。

实现差：「可以改成稳定」不当默认。本页 Lomuto 取尾枢轴，与严式取端点划分步骤不同，最坏触发条件仍是枢轴极偏。

顺序符号表、二分、BST、平衡树概念、散列表。BST 查找是 O(h)：随机插入期望 O(log n)，有序插入退化成链。

散列：均匀假设下平均接近 O(1)，最坏 O(n)。本站二次探查约定 h+i²，全书算例 41 进槽 1；线性探查同一串 41 进 10。开放定址须 α<1，删除常用墓碑。

邻接表上 BFS、DFS 都是 O(V+E)。BFS 得无权最短路。Prim / Kruskal 可处理负权边；Dijkstra 可用于加权有向/无向图，但要求边权非负。

BFS 队列/DFS 栈→访问序不同

Bellman-Ford 能检负环，但标准单源版本只能检出从源点可达的负权环。拓扑只对 DAG。

第 5 部分的单词查找树、子串、正则，408 数据结构只落到「串匹配」薄层。设 1≤m≤n，朴素最坏 Θ((n−m+1)m)；最好成功匹配情形是第一次对齐即匹配、比较 Θ(m)，不能无条件当整个算法最好界。

KMP 主串指针不回退。更细的后缀结构标超纲。

默认实现通常不稳。本站口径：不要把「可改成稳定」写成默认结论。

一个用队列按层扩，一个沿邻接表递归走到底再回溯。本站 7 点图：BFS 为 A B C D E F G，DFS 为 A B D F E C G。

不能。可视化帮建立直觉；严口径 next 仍要自己推。abaabc → 0 1 1 2 2 3。