Algorithms-4th-Edition

动画解析《算法-第四版》代码仓库

这里包含了与我的 B站 视频系列“动画解析《算法-第四版》”相关的所有代码。每个章节都有对应的 java 代码示例。

说明：本仓库中的代码可能会跟本书的官网代码有出入，本书中完整的代码请移步 ☞ 官网，完整的 ☞ 课后习题答案

运行代码

• 需要有一点 java 基础

1. 下载仓库代码

2. 用 IntelliJ IDEA 编辑器打开 Algorithms-4th-Edition 项目

3. 安装依赖, 这是一个 maven 项目

4. 所有代码可直接在 IDEA 编辑器中运行
   部分代码的运行参数存储在 /runConfigurations 下
   可通过 Edit Configurations... 自行修改

目录

1. 【 第一章节 - 算法分析(上) 】
2. 【 第二章节 - 算法分析(中) 】
3. 【 第三章节 - 算法分析(下) 】
4. 【 第四章节 - 优先队列 】
5. 【 第五章节 - 堆排序 】
6. 【 第六章节 - 二叉搜索树 】
7. 【 第七章节 - 平衡二叉搜索树 】
8. 【 第八章节 - 最小生成树 】
9. 【 第九章节 - 子字符串查找 】

---

第一章节 - 算法分析(上)

• ThreeSum-暴力求解:

  • 【算法】计算文件中三元组和为 0 的数量

• 倍率实验

  • 线性回归-确认数学模型 (python)
  • 线性回归-确认数学模型 (java)

---

第二章节 - 算法分析(中)

注意：本章节所有实验数据取决于运行环境，运行结果如有差异请自行判断

• ThreeSum改进

  • ThreeSumFast-第一次改进
  • ThreeSumFinal-第二次改进 (双指针技术)

• 线性回归-拟合数学模型

  • 计算ThreeSumFast-模型 (python)

  • 计算ThreeSumFast-模型 (java)

  • 计算ThreeSumFinal-模型 (python)

  • 计算ThreeSumFinal-模型 (java)

• 实验测试代码

  • 倍率实验-验证模型(输入数字随机)
  • 小数组-验证线性搜索快于二分查找(平均)
  • 小数组-验证冒泡快于快排(平均)
  • 模拟网络编程案例-批量请求vs分批次请求

• 曲线图绘制脚本

  • ThreeSumFast 性能曲线
  • ThreeSumFinal 性能曲线
  • 合并绘制到一张图上

---

第三章节 - 算法分析(下)

• 数据类型大小

  • java中常见的数据类型大小

• 栈内存

  • 估计最大递归深度

• 求第 N 个斐波那契数

  • 递归的方式
  • 迭代法
  • 矩阵指数法

---

第四章节 - 优先队列

• 优先队列 (PQ) 接口

  • PQ 简单接口定义

• 简单实现 PQ

  • 无序数组
  • 无序数组-接口实现(下同)
  • 有序数组
  • 无序链表
  • 有序链表

• 二叉堆实现 PQ

  • 二叉堆实现-简单实现
  • 索引二叉堆实现-简单实现
  • java标准库实现-java.util.PriorityQueue

• 性能测试

  • 测试代码，测试用例为【实验题 2.4.36】
  • 测试用例同上，单独为java标准库 PQ 用的测试代码

第五章节 - 堆排序

• 两种建堆 (大堆) 方式

  • 自上而下
  • 自下而上-常用

• 两种堆排序方式(用大堆进行升序排序)

  • 标准版堆排序实现
  • Floyd 改进版本-较少比较次数

• 计算Floyd优化后和标准堆排序比较、交换次数

  • 统计标准实现元素比较/交换次数
  • 统计Floyd优化后元素比较/交换次数

• 对两种堆排序进行性能测试

  • 输入-普通随机整数
  • 输入-长字符串

第六章节 - 二叉搜索树

• 符号表接口定义

  • 编程接口 API - (key extends Comparable)

• 符号表初级实现

  • 无序链表
  • 有序数组

• 测试插入元素需要的比较次数-绘制曲线图

  • 输入样本：《双城记》，单词长度>=8
  • 可视化-无序链表实现
  • 可视化-有序数组实现

• 二叉搜索树实现

  • 递归实现插入、查找、删除
  • 非递归实现插入、查找、删除

第七章节 - 平衡二叉搜索树

• AVL树

• AVL实现的符号表-官方实现

• 2-3树

• 红黑树实现符号表-官方实现

第八章节 - 最小生成树

• prim算法 (lazy 版本)
• prim算法 (eager 版本)
• kruskal算法

第九章节 - 子字符串字符串查找

• KMP 算法（DFA官方实现)
• 简化版 BM 算法（只实现坏字符规则）- 官方实现