一.順序查找（無序表）：
def sequentialSearch(alist, item):pos = 0found = Falsewhile pos < len(alist) and not found:if alist[pos] == item:found = Trueelse:pos = pos + 1return foundtestlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))?
二.順序查找（有序表）：
def orderedSequentialSearch(alist, item):pos = 0found = Falsestop = Falsewhile pos < len(alist) and not found and not stop:if alist[pos] == item:found = Trueelse:if alist[pos] > item:stop = Trueelse:pos = pos + 1return foundtestlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(orderedSequentialSearch(testlist, 3))
print(orderedSequentialSearch(testlist, 13))?
以下是對兩段代碼的詳細對比分析：
代碼對比：
| 維度 | 無序表順序查找 | 有序表順序查找 |
|---|---|---|
| 核心邏輯 | 逐個比較元素，直到找到目標或遍歷結束 | 逐個比較元素，若當前元素大于目標值則提前終止 |
| 數據要求 | 無要求 | 必須有序（如升序） |
| 提前終止條件 | 僅在找到目標時終止 | 在找到目標或遇到更大元素時終止 |
| 場景 | 無序表時間復雜度 | 有序表時間復雜度 | 說明 |
|---|---|---|---|
| 目標存在于列表中 | O(n/2) | O(n/2) | 平均比較次數相同 |
| 目標不存在于列表中 | O(n) | O(n/2) | 有序表可提前終止，效率提升 |
| 最好情況（目標在首位） | O(1) | O(1) | 一次比較即終止 |
| 最壞情況（目標在末位） | O(n) | O(n) | 需遍歷全量元素 |
| 場景 | 推薦算法 | 原因 |
|---|---|---|
| 數據頻繁變動 | 無序表順序查找 | 維護有序性成本高 |
| 數據有序且查找頻繁 | 有序表順序查找 | 可利用有序性提前終止 |
| 大規模有序數據 | 二分查找（非順序查找） | 時間復雜度 O (log n)，效率更高 |
總結：
- 無序表：實現簡單，適用于小規模或無需維護順序的數據。
- 有序表：通過提前終止優化了查找失敗的場景，但依賴數據有序性。
- 性能提升：僅在查找失敗時顯著提升效率（平均減少約 50% 的比較次數）。
三.二分查找：
對于有序表，二分查找將會是更好的選擇：
def binarySearch(alist, item):first = 0last = len(alist) - 1found = Falsewhile first <= last and not found:midpoint = (first + last) // 2if alist[midpoint] == item:found = Trueelse:if item < alist[midpoint]:last = midpoint - 1else:first = midpoint + 1return foundtestlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))算法核心邏輯：
- 分治思想：每次將搜索范圍縮小一半，直到找到目標或確定目標不存在。
- 關鍵點：
- 有序性：要求輸入列表必須按升序排列。
- 中間點計算：通過?
midpoint = (first + last) // 2?確定當前搜索區間的中間位置。 - 區間調整：
- 若目標值小于中間值，搜索左半區間（
last = midpoint - 1）。 - 若目標值大于中間值，搜索右半區間（
first = midpoint + 1）。
- 若目標值小于中間值，搜索左半區間（
四.冒泡排序：
?
def bubbleSort(alist):for passnum in range(len(alist)-1, 0, -1):for i in range(passnum):if alist[i] > alist[i+1]:temp = alist[i]alist[i] = alist[i+1]alist[i+1] = tempalist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubbleSort(alist)
print(alist)冒泡排序相對較為簡單，所以對于代碼邏輯不加以過多贅述，但是此代碼存在些許缺點，我們可以進行相應的改進：
優化：
def shortBubbleSort(alist):exchanges = Truepassnum = len(alist) - 1while passnum > 0 and exchanges:exchanges = Falsefor i in range(passnum):if alist[i] > alist[i + 1]:exchanges = Truetemp = alist[i]alist[i] = alist[i + 1]alist[i + 1] = temppassnum = passnum - 1alist = [20, 30, 40, 90, 50, 60, 70, 80, 100, 110]
shortBubbleSort(alist)
print(alist)?這段 Python 代碼實現了短冒泡排序（優化的冒泡排序）算法，通過設置?exchanges?標志來判斷某一輪排序中是否發生了交換，若未發生交換則提前終止排序過程，以優化性能，最后對給定列表進行排序并輸出 。
五.選擇排序：
def selectionSort(alist):for fillslot in range(len(alist)-1, 0, -1):positionOfMax = 0for location in range(1, fillslot + 1):if alist[location] > alist[positionOfMax]:positionOfMax = locationtemp = alist[fillslot]alist[fillslot] = alist[positionOfMax]alist[positionOfMax] = temp?這段代碼實現了選擇排序算法，其基本思想是：每次從未排序的部分中找到最大（這里是升序排序，找最大元素放到未排序部分末尾 ）的元素，與未排序部分的最后一個元素交換位置，逐步完成列表的排序 。
六.插入排序：
def insertionSort(alist):for index in range(1, len(alist)):currentvalue = alist[index]position = indexwhile position > 0 and alist[position - 1] > currentvalue:alist[position] = alist[position - 1]position = position - 1alist[position] = currentvalue?這段 Python 代碼實現了插入排序算法，其工作原理是：從列表的第二個元素開始，將當前元素（currentvalue）依次與前面已排序部分的元素進行比較，如果前面元素大于當前元素，就將前面元素后移，直到找到當前元素應該插入的位置，最后將當前元素插入到該位置，逐步構建有序列表 。
