D1模块六类基础算法初探

由于 Desicion Math与其它更专注计算量的数学模块不同，在 D1模块中各位考生会首先接触到一些基础但至关重要的算法。本文将由理综教研部老师针对该模块第一章的六个小节，主要涉及的两种排序算法 (冒泡排序、快速排序)和三种装箱算法 (首适应算法、首适应递减算法、满箱算法)以及一种查找算法 (二分查找法)做切片分享，还请详读。

模块技法

算法浅述‍‍

『冒泡排序』

冒泡排序是一种简单直观的排序算法，它重复地遍历要排序的列表，由列表中的第一个元素开始依次比较两个元素，如顺序错误就将它们交换。持续遍历整个列表，直到没有需要交换的元素，直到整个列表有序。

来源：理综教研部模拟作答过程图

易错点：

1.数据已有序后，还需写一次 pass的结果

2.对 n个数据进行冒泡排序，最多需n次 pass，n(n-1)/2 次 comparation/swap，最少需要 1次 pass。但此处应注意，有 comparation但不一定产生 swap‍

3. 当升序最小值在最后面，例如升序：2 3 4 5 1，降序最大值在最后面时，例如降序：4 3 2 1 5，冒泡排序法需要 n次 pass

4. 当序列已是题目要求的顺序排列时，冒泡排序法只需1次 pass

来源：理综教研部模拟作答过程图

『快速排序』

快速排序是一种高效的排序算法，首先选择一个基准元素 (通常是列表中的中间或者右侧元素)，并将一个列表分成两个子列表，小于基准的放在左边 (升序排列)，大于基准的放在右边，递归地对子列表进行快速排序，然后合并这两个子列表得到有序的列表。

来源：理综教研部模拟作答过程图

易错点：

1. pivot的选取方法：先把当前列表中的数据数量加 1，再除以 2得到值 c，若c为整数，则直接取第 c个数作为 pivot，若c为非整数，则向大取整，找到对应的值作为 pivot

2. 理综教研部温馨提示：若数据与 pivot相等，则保持原顺序不变‍

3. 要注意审清题干要求需要使用的排序算法，进行升序还是降序排列

来源：理综教研部模拟作答过程图

『装箱算法』

首适应算法：一种动态装箱算法，用于将一组物品从第一个箱子开始依次放入固定容量的箱子中，直到装不下为止。若当前箱子无法容纳新的物品，则创建新的箱子。重复以上步骤，直到所有物品都被装入箱子。

来源：理综教研部模拟作答过程图

易错点：

1. 注意箱子的容量设置，避免出现装箱过于紧凑或浪费空间的情况

2. 注意检查是否有漏写，重复数据

首适应递减算法：此为首适应算法的改进版本，先将数据进行了降序排列，再对数据进行首适应算法。

易错点：

1. 对数据进行排序时，应注意是否按照降序进行排列，是否有遗漏数据或者重复数据

2. 装箱完毕后，还应注意箱子是否超过了容量

来源：理综教研部模拟作答过程图

满箱算法：这是一种贪心算法，先找满箱组合，再将剩余数据进行首适应算法装箱，尽可能多地将箱子装满。

来源：理综教研部模拟作答过程图

易错点：

注意 lowerbound的计算和作答格式以及满箱组合的找法。

来源：理综教研部模拟作答过程图‍

『二分查找法』

二分查找法是一种高效的查找算法，要求被查找的数据是有序的。在确定查找范围的起始和结束位置后，计算中间位置的索引。比较中间位置的元素与目标值的关系，缩小查找范围。重复以上步骤，直到找到目标值或查找范围为空。

来源：理综教研部模拟作答过程图

易错点：

1. 数据必须是有序的，否则无法使用二分查找。

2. 确保边界情况的处理，如空列表或目标值不存在的情况。

3. 二分查找次数的计算公式：次数=

4. pivot的选取与快速排序的找法要一致。

来源：理综教研部模拟作答过程图

通过对这六个小节中的算法进行深入了解，我们不仅能够掌握其基本原理和流程，还能够更好地理解算法的应用场景和优劣势。在学习过程中，理综教研部强调各位考生注意算法本身的应用，更需关注其中的易错点，在实际应用中能更加得心应手。希望本文能够帮助读者更好地理解和应用这些经典的数据结构与算法。