Python[数据结构及算法 --- 查找]

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

def sequentialSearch(alist, item):
    pos = 0
    found = False

    while pos < len(alist) and not found:
        if alist[pos] == item:
            found = True
        else:
            pos = pos + 1

    return found


testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

二.顺序查找（有序表）：

def orderedSequentialSearch(alist, item):
    pos = 0
    found = False
    stop = False
    while pos < len(alist) and not found and not stop:
        if alist[pos] == item:
            found = True
        else:
            if alist[pos] > item:
                stop = True
            else:
                pos = pos + 1
    return found


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(orderedSequentialSearch(testlist, 3))
print(orderedSequentialSearch(testlist, 13))

以下是对两段代码的详细对比分析：

代码对比：

总结：

• 无序表：实现简单，适用于小规模或无需维护顺序的数据。
• 有序表：通过提前终止优化了查找失败的场景，但依赖数据有序性。
• 性能提升：仅在查找失败时显著提升效率（平均减少约 50% 的比较次数）。

三.二分查找：

对于有序表，二分查找将会是更好的选择：

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1

    return found


testlist = [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] = temp

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubbleSort(alist)
print(alist)

冒泡排序相对较为简单，所以对于代码逻辑不加以过多赘述，但是此代码存在些许缺点，我们可以进行相应的改进：

优化：

def shortBubbleSort(alist):
    exchanges = True
    passnum = len(alist) - 1
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                exchanges = True
                temp = alist[i]
                alist[i] = alist[i + 1]
                alist[i + 1] = temp
        passnum = passnum - 1


alist = [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 = 0
        for location in range(1, fillslot + 1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location

        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp

 这段代码实现了选择排序算法，其基本思想是：每次从未排序的部分中找到最大（这里是升序排序，找最大元素放到未排序部分末尾 ）的元素，与未排序部分的最后一个元素交换位置，逐步完成列表的排序 。

六.插入排序：

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position - 1] > currentvalue:
            alist[position] = alist[position - 1]
            position = position - 1

        alist[position] = currentvalue

 这段 Python 代码实现了插入排序算法，其工作原理是：从列表的第二个元素开始，将当前元素（currentvalue）依次与前面已排序部分的元素进行比较，如果前面元素大于当前元素，就将前面元素后移，直到找到当前元素应该插入的位置，最后将当前元素插入到该位置，逐步构建有序列表 。