第16章算法-排序与搜寻

16.1 算法（alogrithm）

算法是指一个寻求解答的过程的程序代码。

程序实例：

# 寻找最大值的算法
data = [10, 25, 38, 69, 83]
max = data[0]
for num in data:
    if num > max:
        max = num
print("最大值：", max)

执行结果：

最大值： 83

16.2 排序

在排序方法中最著名也最简单的算法是泡沫排序法（Bubble Sort）或者叫冒泡排序。其基本原理是将相邻的元素进行比较，如果前一个元素的值大于后一个元素，则交换两个元素的位置，这样经过一次循环后，最大的元素会被放到最右边，持续这样的动作，直到所有的元素都被排好顺序。

冒泡排序算法如下：

for i in range(0, len(列表)):     # 外层循环
    for j in range(0, len(列表) - 1 - i):        # 内层循环
        if 列表[j] > 列表[j+1]:
            交换列表[j]与列表[j+1]的内容

程序实例：

def bubbleSort(nLst):
    length = len(nLst)
    for i in range(length-1):
        print("第 %d 次外圈排序" % (i+1))
        for j in range(length-1-i):
            if nLst[j] > nLst[j+1]:
                nLst[j],nLst[j+1] = nLst[j+1],nLst[j]
            print("第 %d 次内圈排序：" % (j+1), nLst)
    return nLst
data = [32, 19, 66, 81, 4]
print("原始列表：", data)
print("排序结果：", bubbleSort(data))

执行结果：
在这里插入图片描述

16.3 搜寻（search）

16.3.1 顺序搜寻法（sequential search）

也叫顺序查找，将数据逐个拿来与搜寻值（key）做比对，直到找到与搜寻值相同的数据或是所有数据搜寻结束为止。它的演算方法如下：

for i in range(len(列表)):
    if key == 列表[i]
    return i

程序实例：

def sequentialSearch(nLst):
    for i in range(len(nLst)):
        if nLst[i] == key:
            return i            # 返回索引值
    return -1                   # 找不到，返回-1
data = [1, 3, 5, 7, 24, 13]
key = int(input("请输入搜寻值："))
result = sequentialSearch(data)
if result != -1:
    print("在 %d 索引位置找到了 %d，共找了 %d 次" % (result, key, (result+1)))
else:
    print("未找到该值！")

执行结果：
在这里插入图片描述

16.3.2 二分搜寻法（binary search）

要执行二分搜寻法，首先要对数据进行排序（从小到大排），然后将搜寻值（key）与中间值进行比较，如果搜寻值大于中间值，则下一次往右边（较大值边）搜寻，否则往左边（较小值边）搜寻。上述动作持续进行，直到找到搜寻值或是所有数据搜寻结束才停止。它的演算方法如下：

# 默认已将搜寻数据排序存至列表
middle = int((low + high) / 2)            # low为排序后第一个元素值的索引，high为最后一个元素值的索引，通过运算获得中间索引值
search_count = 0                        # 将搜寻次数设为0
while True:
    search_count += 1                    # 搜寻次数加1
    if key == list[middle]:                # 若key的值与list[middle]相等，置result的值为middle，离开循环，搜寻结束
        result = middle
        break
    elif key > list[middle]:            # 若key的值大于list[middle]的值，说明list[middle]前面的值都比key小
        low = middle + 1                # 下一次需往右搜寻，修改low索引值
    else:
        high = middle - 1                # 下一次需要往左搜寻，修改high索引值
    middle = int((low + high) / 2)        # 更新中间索引
    if low > high:                        # 所有元素比较结束
        result = -1
        break

程序实例：

def binarySearch(nLst):
    print("打印搜寻列表：",nLst)
    low = 0                 # 最小索引，初始值为列表的最小索引值
    high = len(nLst) - 1    # 最大索引，初始值为列表的最大索引值
    middle = int((low + high) / 2)  # 中间索引
    search_count = 0            # 搜寻次数
    while True:
        search_count += 1
        if key == nLst[middle]:
            result = middle
            break
        elif key > nLst[middle]:
            low = middle + 1            # 下一次往右搜寻
        else:
            high = middle - 1           # 下一次往左搜寻
        middle = int((low + high) / 2)  # 更新中间索引
        if low > high:                  # 所有元素比较结束
            result = -1
            break
    return result, search_count
data = [24, 18, 7, 23, 31, 49, 37, 5, 13, 21]
sequentialData = sorted(data)       # 对列表进行排序
key = int(input("请输入搜寻值："))
index, times = binarySearch(sequentialData)
if index != -1:
    print("在 %d 索引位置找到了 %d，共找了 %d 次" % (index, key,times))
else:
    print("未找到该值！")