D1模塊六類基礎算法初探

由於(yu) Desicion Math與(yu) 其它更專(zhuan) 注計算量的數學模塊不同，在 D1模塊中各位考生會(hui) 首先接觸到一些基礎但至關(guan) 重要的算法。本文將由理綜教研部老師針對該模塊第一章的六個(ge) 小節，主要涉及的兩(liang) 種排序算法 (冒泡排序、快速排序)和三種裝箱算法 (首適應算法、首適應遞減算法、滿箱算法)以及一種查找算法 (二分查找法)做切片分享，還請詳讀。

模塊技法

算法淺述‍‍

『冒泡排序』

冒泡排序是一種簡單直觀的排序算法，它重複地遍曆要排序的列表，由列表中的第一個(ge) 元素開始依次比較兩(liang) 個(ge) 元素，如順序錯誤就將它們(men) 交換。持續遍曆整個(ge) 列表，直到沒有需要交換的元素，直到整個(ge) 列表有序。

來源：理綜教研部模擬作答過程圖

易錯點：

1.數據已有序後，還需寫(xie) 一次 pass的結果

2.對 n個(ge) 數據進行冒泡排序，最多需n次 pass，n(n-1)/2 次 comparation/swap，最少需要 1次 pass。但此處應注意，有 comparation但不一定產(chan) 生 swap‍

3. 當升序最小值在最後麵，例如升序：2 3 4 5 1，降序最大值在最後麵時，例如降序：4 3 2 1 5，冒泡排序法需要 n次 pass

4. 當序列已是題目要求的順序排列時，冒泡排序法隻需1次 pass

來源：理綜教研部模擬作答過程圖

『快速排序』

快速排序是一種高效的排序算法，首先選擇一個(ge) 基準元素 (通常是列表中的中間或者右側(ce) 元素)，並將一個(ge) 列表分成兩(liang) 個(ge) 子列表，小於(yu) 基準的放在左邊 (升序排列)，大於(yu) 基準的放在右邊，遞歸地對子列表進行快速排序，然後合並這兩(liang) 個(ge) 子列表得到有序的列表。

來源：理綜教研部模擬作答過程圖

易錯點：

1. pivot的選取方法：先把當前列表中的數據數量加 1，再除以 2得到值 c，若c為(wei) 整數，則直接取第 c個(ge) 數作為(wei) pivot，若c為(wei) 非整數，則向大取整，找到對應的值作為(wei) pivot

2. 理綜教研部溫馨提示：若數據與(yu) pivot相等，則保持原順序不變‍

3. 要注意審清題幹要求需要使用的排序算法，進行升序還是降序排列

來源：理綜教研部模擬作答過程圖

『裝箱算法』

首適應算法：一種動態裝箱算法，用於(yu) 將一組物品從(cong) 第一個(ge) 箱子開始依次放入固定容量的箱子中，直到裝不下為(wei) 止。若當前箱子無法容納新的物品，則創建新的箱子。重複以上步驟，直到所有物品都被裝入箱子。

來源：理綜教研部模擬作答過程圖

易錯點：

1. 注意箱子的容量設置，避免出現裝箱過於(yu) 緊湊或浪費空間的情況

2. 注意檢查是否有漏寫(xie) ，重複數據

首適應遞減算法：此為(wei) 首適應算法的改進版本，先將數據進行了降序排列，再對數據進行首適應算法。

易錯點：

1. 對數據進行排序時，應注意是否按照降序進行排列，是否有遺漏數據或者重複數據

2. 裝箱完畢後，還應注意箱子是否超過了容量

來源：理綜教研部模擬作答過程圖

滿箱算法：這是一種貪心算法，先找滿箱組合，再將剩餘(yu) 數據進行首適應算法裝箱，盡可能多地將箱子裝滿。

來源：理綜教研部模擬作答過程圖

易錯點：

注意 lowerbound的計算和作答格式以及滿箱組合的找法。

來源：理綜教研部模擬作答過程圖‍

『二分查找法』

二分查找法是一種高效的查找算法，要求被查找的數據是有序的。在確定查找範圍的起始和結束位置後，計算中間位置的索引。比較中間位置的元素與(yu) 目標值的關(guan) 係，縮小查找範圍。重複以上步驟，直到找到目標值或查找範圍為(wei) 空。

來源：理綜教研部模擬作答過程圖

易錯點：

1. 數據必須是有序的，否則無法使用二分查找。

2. 確保邊界情況的處理，如空列表或目標值不存在的情況。

3. 二分查找次數的計算公式：次數=

4. pivot的選取與(yu) 快速排序的找法要一致。

來源：理綜教研部模擬作答過程圖

通過對這六個(ge) 小節中的算法進行深入了解，我們(men) 不僅(jin) 能夠掌握其基本原理和流程，還能夠更好地理解算法的應用場景和優(you) 劣勢。在學習(xi) 過程中，理綜教研部強調各位考生注意算法本身的應用，更需關(guan) 注其中的易錯點，在實際應用中能更加得心應手。希望本文能夠幫助讀者更好地理解和應用這些經典的數據結構與(yu) 算法。