算法（第 4 版）

📖 本书核心内容

《算法（第 4 版）》是算法领域的经典教材，首次出版于 2011 年。Robert Sedgewick（Google 副总裁、普林斯顿大学教授）和 Kevin Wayne 以 Java 语言实现，系统阐述了排序、搜索、图、字符串等核心算法。

本书采用算法实现、理论分析、实际应用相结合的教学方法，提供了丰富的可视化示例和编程练习。配套的算法可视化网站（algs4.cs.princeton.edu）是学习算法的绝佳资源。本书的核心理念是：算法不仅是理论，更是实践——每个算法都应该用代码实现，并用实际数据测试。

🎯 核心模块一：算法分析与排序算法

算法分析是算法学习的基础。大 O 记号用于描述算法的渐近时间复杂度，最坏情况用于保证算法的性能上限，平均情况用于评估算法的实际表现，均摊分析用于评估一系列操作的平均成本。理解算法分析是选择合适算法的前提——没有绝对"最好"的算法，只有最适合特定场景的算法。

排序是算法学习的基础。选择排序每次从未排序部分选择最小元素，时间复杂度 O(n²)，实现简单但效率低。插入排序将每个元素插入到已排序部分的正确位置，时间复杂度 O(n²)，但对部分有序数据效率高。希尔排序是插入排序的改进版，通过增量序列加速，时间复杂度 O(n^1.3)。归并排序采用分治策略，将数组分成两半分别排序后合并，时间复杂度 O(n log n)，需要额外空间。快速排序也采用分治策略，选择基准元素将数组分成两部分递归排序，平均时间复杂度 O(n log n)，最坏 O(n²)。堆排序利用堆数据结构排序，时间复杂度 O(n log n)，原地排序。

排序算法的选择取决于具体场景。对于小规模数据，插入排序可能是最佳选择——虽然时间复杂度高，但常数因子小。对于大规模数据，归并排序和快速排序是主流选择。归并排序保证 O(n log n) 最坏情况，但需要额外空间；快速排序平均性能更好，但最坏情况 O(n²)。在实际应用中，许多标准库（如 Java 的 Arrays.sort）采用混合策略：小规模数据使用插入排序，大规模数据使用快速排序或归并排序。

🎯 核心模块二：搜索算法与数据结构

搜索是算法学习的核心。二分查找在有序数组中实现 O(log n) 的对数级搜索，是最高效的搜索算法之一。二叉查找树（BST）是动态有序符号表，平均时间复杂度 O(log n)，最坏 O(n）。红黑树是自平衡二叉查找树，保证最坏情况 O(log n），是 Java 中 TreeMap 和 TreeSet 的底层实现。散列表（Hash Table）基于哈希函数实现 O(1) 的平均搜索时间，是 Java 中 HashMap 和 HashSet 的底层实现。分离链接法和线性探测法是解决哈希冲突的两种主要方法。

数据结构是算法的载体。栈（Stack）是后进先出（LIFO）数据结构，适用于括号匹配、函数调用、撤销操作等场景。队列（Queue）是先进先出（FIFO）数据结构，适用于任务调度、广度优先搜索、生产者-消费者模型等场景。优先队列（Priority Queue）支持删除最大/最小元素，是堆排序和 Dijkstra 算法的基础。堆（Heap）是优先队列的高效实现，分为最大堆和最小堆。

图（Graph）是由顶点和边组成的数据结构，是社交网络、地图导航、网页链接等现实问题的抽象。树（Tree）是层次结构的数据结构，是文件系统、DOM 树、决策树等应用的基础。理解数据结构的特性是选择合适算法的前提——不同的数据结构适用于不同的操作模式。

🎯 核心模块三：图算法与字符串算法

图算法是算法学习的高级主题。深度优先搜索（DFS）沿着一条路径尽可能深入，然后回溯，适用于连通性检测、拓扑排序、强连通分量等场景。广度优先搜索（BFS）逐层访问所有顶点，适用于最短路径（无权图）、层次遍历等场景。拓扑排序是有向无环图的线性排序，适用于任务调度、依赖解析等场景。强连通分量是有向图中的强连通子图，适用于社交网络分析、网页链接分析等场景。最小生成树（MST）是连接所有顶点的最小权重边集合，Prim 算法和 Kruskal 算法是两种经典解法。最短路径（Shortest Path）是两点之间的最小权重路径，Dijkstra 算法适用于非负权重，Bellman-Ford 算法适用于负权重。

字符串算法是算法学习的实用主题。字符串排序包括：键索引计数、LSD 字符串排序、MSD 字符串排序、三向字符串快速排序。模式匹配包括：KMP 算法（线性时间模式匹配）、Boyer-Moore 算法（从右向左匹配）、Rabin-Karp 指纹字符串查找（哈希方法）。正则表达式匹配是文本处理的核心技术，NFA 模拟是正则表达式匹配的经典方法。数据压缩包括：霍夫曼编码（基于字符频率的变长编码）、LZW 编码（基于字典的压缩算法）。

⭐ 金句摘录

"算法是计算机科学的基石。"

"好的算法可以让程序运行得更快，使用更少的内存。"

"排序和搜索是算法学习的基础，图算法是算法学习的高级主题。"

"算法分析的目的是预测程序的性能，指导算法选择。"

"理解算法的实现细节，比记住算法的名字更重要。"

📚 阅读建议

适合计算机科学专业学生和有编程基础的开发者，配合在线可视化工具学习重点掌握排序搜索图算法。