我们通过考虑动态连通性问题来说明我们开发和分析算法的基本方法。我们介绍了联合查找数据类型，并考虑了几种实现方法（快速查找、快速联合、加权快速联合和带路径压缩的加权快速联合）。最后，我们将联合-查找数据类型应用于物理化学中的渗流问题。

我们分析算法性能的基础是科学方法。我们首先进行计算实验，测量程序的运行时间。我们利用这些测量结果提出有关性能的假设。接下来，我们创建数学模型来解释它们的行为。最后，我们考虑分析 Java 程序的内存使用情况。

我们考虑了两种用于存储对象集合的基本数据类型：堆栈和队列。我们使用单链表或调整大小的数组来实现这两种数据类型。我们引入了两个高级 Java 功能--泛型和迭代器，它们可以简化客户端代码。最后，我们考虑了栈和队列的各种应用，包括解析算术表达式和模拟队列系统。

我们将介绍排序问题和 Java 的 Comparable 接口。我们研究了两种基本排序方法（选择排序和插入排序）以及其中一种方法的变体（shellsort）。我们还考虑了均匀洗牌数组的两种算法。最后，我们通过格雷厄姆扫描算法将排序应用于计算凸壳。

我们对合并排序算法进行了研究，结果表明，该算法能保证以最多 n lg n 次比较对包含 n 个项的任何数组进行排序。我们还考虑了一个非递归、自下而上的版本。我们证明，任何基于比较的排序算法在最坏情况下都必须至少进行 n lg n 次比较。我们将讨论对排序对象使用不同的排序方式以及相关的稳定性概念。

我们介绍并实现了随机 quicksort 算法，并对其性能进行了分析。我们还考虑了随机 quickselect，这是一种 quicksort 变种，能在线性时间内找到第 k 个最小项。最后，我们考虑了 3-way quicksort，这是 quicksort 的一种变体，在存在重复键的情况下尤其有效。

我们介绍了优先队列数据类型和使用二进制堆数据结构的高效实现方法。这种实现方式还带来了一种高效的排序算法--堆排序。最后，我们将介绍优先队列的一个应用，即模拟受弹性碰撞定律影响的 n 个粒子的运动。

我们定义了符号表（也称为关联数组、映射或字典）的应用程序接口，并描述了使用排序数组（二进制搜索）和无序列表（顺序搜索）的两种基本实现。当键为可比较键时，我们定义了一个扩展的应用程序接口，其中包括额外的 min、max floor、 ceiling、rank 和 select 方法。为了开发该应用程序接口的高效实现，我们研究了二进制搜索树数据结构并分析了其性能。

在本讲座中，我们的目标是开发一种符号表，保证搜索和插入（以及许多其他操作）的对数性能。我们将从 2-3 棵树开始，这很容易分析，但很难实现。接下来，我们考虑红黑二叉搜索树，我们认为这是一种将 2-3 树作为二叉搜索树来实现的新方法。最后，我们介绍 B 树，它是 2-3 树的广义化，被广泛用于实现文件系统。

我们从一维和二维范围搜索开始，目标是找到给定一维或二维范围内的所有点。为此，我们考虑 kd 树，当关键点是平面（或更高维度）上的点时，kd 树是 BST 的自然概括。我们还考虑了交集问题，其目标是找到一组线段或矩形之间的所有交集。

我们首先介绍哈希函数的理想特性以及如何在 Java 中实现这些特性，包括一个基本原则，即统一哈希假设，它是哈希应用取得成功的潜在基础。然后，我们考虑了实现哈希表的两种策略--分离链和线性探测。在统一散列假设下，这两种策略都能产生恒定时间的搜索和插入性能。

我们考虑了符号表的各种应用，包括集合、字典客户端、索引客户端和稀疏向量。