【Java数据结构】05-查找、排序（散列,ASL）

6 查找

期末考试的大题中考察了线性探测法，需写出过程

做题辅助

bilibili视频

6.1 理解查找的定义

当我们谈论“查找”时，通常指的是在一组数据中寻找特定元素的过程。查找的目标是确定某个值是否存在于给定的数据集合中，并且如果存在，可能还需要找到其具体的位置或其他相关信息。

查找操作在计算机科学和信息处理中是非常常见且重要的，因为我们经常需要在大量数据中快速找到所需的信息。查找问题可以分为多种情况，取决于数据集合的特性以及我们需要的结果。

以下是一些常见的查找算法和情境：

1. 线性查找： 逐个检查数据集合中的元素，直到找到目标值或遍历完整个集合。

2. 二分查找： 仅适用于已排序的数据集合。通过比较目标值和中间元素的大小，将查找范围缩小一半，直到找到目标值或确定不存在。

3. 哈希查找： 利用哈希函数将目标值映射到集合中的一个位置，快速定位所需元素。

4. 树结构查找（例如二叉搜索树）： 通过有序的树结构，根据节点值的大小关系逐步缩小查找范围，以快速找到目标值。

5. 图搜索： 在图结构中查找特定节点或路径。

查找的效率取决于数据集合的大小、性质以及所使用的算法。选择适当的查找算法对于提高程序性能非常重要。

6.2 掌握对查找算法进行衡量的一些指标：平均查找长度、成功查找的查找长度、查找不成功的查找长度

当我们评估查找算法时，常用的一些指标包括：

1. 平均查找长度（Average Search Length，ASL）： 这是在平均情况下查找到目标元素所需的比较次数。对于成功和不成功的查找，ASL 可以分别计算。

2. 成功查找的平均查找长度（ASL for Successful Search）： 在查找成功的情况下，平均需要多少次比较才能找到目标元素。

3. 不成功查找的平均查找长度（ASL for Unsuccessful Search）： 在查找不成功的情况下，平均需要多少次比较才能确定目标元素不在集合中。

这些指标的计算方式可能会根据具体的查找算法和数据集合的性质而有所不同。以下是一些常见的情况：

• 线性查找： 对于一个包含 n 个元素的列表，平均查找长度 ASL = (n + 1) / 2。这是因为平均情况下，目标元素在列表中的位置可能是任何位置，所以平均查找长度是所有可能位置的平均值。

• 二分查找： 在有序列表中，二分查找的平均查找长度取决于列表的长度。对于 n 个元素的列表，ASL = log?(n) + 1。

这些指标提供了评估查找算法效率的一种方式。在选择查找算法时，我们通常希望使用平均查找长度较小的算法，因为它在平均情况下表现更好。

6.3 掌握顺序查找和折半查找法，理解二者之间的异同点

顺序查找和折半查找（二分查找）是两种不同的查找算法，它们在实现方式和性能方面有一些明显的差异。以下是它们之间的一些异同点：

顺序查找（Sequential Search）：

1. 实现方式： 顺序查找是一种逐个检查数据元素的方法，从数据集合的起始位置开始，逐个比较元素，直到找到目标元素或遍历整个集合。

2. 数据集合要求： 不对数据集合的有序性有特殊要求，适用于无序列表或数组。

3. 时间复杂度： 在最坏情况下，需要遍历整个数据集合，时间复杂度为 O(n)，其中 n 是数据元素的数量。

4. 适用性： 适用于小型数据集合或者对数据集合没有特殊排序要求的情况。

折半查找（Binary Search）：

1. 实现方式： 折半查找是一种基于有序数据集合的算法。它通过比较目标值与中间元素的大小关系，将查找范围缩小一半，从而快速定位目标元素的位置。

2. 数据集合要求： 数据集合必须有序，通常要求升序或降序排列。

3. 时间复杂度： 每次比较后，查找范围减半，因此时间复杂度为 O(log n)，其中 n 是数据元素的数量。

4. 适用性： 适用于大型有序数据集合，尤其在需要频繁查找的情况下，效率更高。

异同点总结：

• 有序性要求： 顺序查找不要求数据有序，而折半查找要求数据有序。

• 时间复杂度： 折半查找的平均时间复杂度较低，适用于大型有序数据集合；而顺序查找的时间复杂度相对较高，适用于小型数据集合或者无序数据集合。

• 实现思想： 顺序查找是逐个比较的思想，而折半查找是通过不断缩小查找范围的思想。

6.4 掌握散列技术，包括散列函数、散列表、散列冲突的发生及其解决方法、负载因子

散列技术是一种用于快速查找的数据结构，它涉及到散列函数、散列表、散列冲突和负载因子等概念。让我一一解释：

1. 散列函数（Hash Function）

散列函数将输入数据映射为固定大小的散列码（哈希值）。好的散列函数应该满足以下特点：

• 确定性： 对于相同的输入，散列函数应该始终产生相同的散列码。

• 高效性： 计算散列码的过程应该是高效的，不会成为性能瓶颈。

• 均匀性： 散列函数应该将不同的输入均匀地映射到散列码空间，以减少冲突的可能性。

2. 散列表（Hash Table）

散列表是一个包含键值对的数据结构，其中每个键通过散列函数映射到一个唯一的索引（散列码）。通过这个索引，我们可以直接访问对应的值。散列表的实现通常包括一个数组和一个散列函数。

3. 散列冲突（Collision）

散列冲突是指两个不同的键被映射到相同的散列码。冲突可能导致数据丢失或存储位置的混乱。解决散列冲突的方法包括：

• 开放寻址法（Open Addressing）： 尝试找到下一个可用的位置来存储冲突的键。

• 链地址法（Chaining）： 将多个键映射到同一位置的冲突键存储在一个链表中。

4. 负载因子（Load Factor）

负载因子是散列表中已存储键值对数与散列表总大小的比率。它用于衡量散列表的装载程度。负载因子的高低影响散列表的性能。

• 负载因子 = 已存储键值对数 / 散列表总大小

通常，负载因子越高，冲突的可能性越大，性能可能降低。当负载因子超过某个阈值时，可以考虑扩展散列表的大小，以保持合适的装载程度。

7 排序

7.1 掌握排序的稳定性

在计算机科学中，排序算法的稳定性是指如果两个元素的关键字相等，它们在排序后的相对位置是否保持不变。具体而言，如果在排序前，元素A在元素B之前，而且在排序后仍然在元素B之前，那么这个排序算法就是稳定的。

为了更好地理解排序的稳定性，让我们以一个例子说明：

假设有一个包含学生信息的表格，其中包含学生的姓名和考试成绩。我们希望按照成绩对学生进行排序，但是在成绩相同时，我们想保持他们在表格中的原始顺序。这就是排序的稳定性的应用场景。

下面是一个简单的例子，展示了一个稳定排序和一个不稳定排序的区别：

假设原始数据为：(姓名, 成绩)

(John, 90)
(Jane, 85)
(Bob, 90)
(Alice, 80)

如果我们使用稳定排序算法，例如稳定的归并排序，对成绩进行排序，得到的结果可能是：

(Alice, 80)
(Jane, 85)
(John, 90)
(Bob, 90)

可以看到，成绩相同的学生 John 和 Bob 在排序后的相对位置保持不变，这就是稳定排序的特性。

而如果我们使用不稳定排序算法，例如快速排序，得到的结果可能是：

(Alice, 80)
(Jane, 85)
(Bob, 90)
(John, 90)

在这里，成绩相同的 John 和 Bob 的相对位置可能发生变化，因此这是一个不稳定排序。

掌握排序的稳定性对于特定应用场景非常重要，特别是在涉及到维护相对顺序的情况下。

7.2 对直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序、基数排序这些算法，掌握具体的排序过程集排序特点，并掌握时间复杂度、空间复杂度以及是否稳定等方面的特点

排序算法	过程	特点	时间复杂度	空间复杂度	稳定性
直接插入排序	逐个将元素插入已排好序的子序列	简单，适用于小规模数据或基本有序的数据	最好：O(n)，最坏/平均：O(n^2)	O(1)	稳定
冒泡排序	通过相邻元素的比较和交换	简单，适用于小规模数据或基本有序的数据	最好：O(n)，最坏/平均：O(n^2)	O(1)	稳定
简单选择排序	选择未排序部分的最小（或最大）元素	比较次数与初始顺序无关，适用于链式结构	最好/最坏/平均：O(n^2)	O(1)	不稳定
快速排序	通过一趟排序将数据分割成独立的两部分	高效，分治策略	最好/平均：O(nlogn)，最坏：O(n^2)	O(logn)	不稳定
堆排序	构建堆，然后每次将堆顶元素与堆尾元素交换	高效，原地排序	最好/最坏/平均：O(nlogn)	O(1)	不稳定
归并排序	将序列分成两部分，分别排序，然后合并两个有序序列	稳定，适用于大规模数据和外部排序	最好/最坏/平均：O(nlogn)	O(n)	稳定
基数排序	从低位到高位，依次对每一位进行排序	适用于整数，稳定	最好/最坏/平均：O(d*(n+r))	O(n+r)	稳定

7.3 具有在不同的应用需求下，能够根据各种排序算法特点选择合适排序算法的能力

排序算法	稳定性	适用场景	备注
冒泡排序（Bubble Sort）	稳定	小型数据集、基本有序的数据	简单但效率较低，适用于小规模数据或基本有序数据。
插入排序（Insertion Sort）	稳定	部分有序的数据、小型数据集	对于基本有序的数据性能较好，适用于小型数据集。
选择排序（Selection Sort）	不稳定	小型数据集、数据移动成本较高	简单但不稳定，适用于小型数据集，对于数据移动成本较高的场景。
归并排序（Merge Sort）	稳定	大型数据集	适用于大规模数据集，性能较为稳定，但需要额外的空间。
快速排序（Quick Sort）	不稳定	大型数据集	平均性能较好，适用于大规模数据集，原地排序。
堆排序（Heap Sort）	不稳定	大型数据集、原地排序	堆排序的主要优势在于原地排序，适用于大规模数据集，但不稳定。
计数排序（Counting Sort）	稳定	非负整数数据，数据分布较均匀	适用于非负整数数据，线性时间复杂度，但对数据范围有一定要求。
基数排序（Radix Sort）	稳定	整数数据，根据位进行排序	适用于整数数据，按照位数排序，对于位数较小的整数较为有效。