一.顺序查找（无序表）：

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))

算法核心逻辑：

• 分治思想：每次将搜索范围缩小一半，直到找到目标或确定目标不存在。
• 关键点：
  1. 有序性：要求输入列表必须按升序排列。
  2. 中间点计算：通过 midpoint = (first + last) // 2 确定当前搜索区间的中间位置。
  3. 区间调整：
     • 若目标值小于中间值，搜索左半区间（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）依次与前面已排序部分的元素进行比较，如果前面元素大于当前元素，就将前面元素后移，直到找到当前元素应该插入的位置，最后将当前元素插入到该位置，逐步构建有序列表 。