《Python零基础快乐学习之旅》学习笔记16——算法-排序与搜寻

素颜马尾好姑娘i 2022-10-27 01:40 162阅读 0赞

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

执行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VzZXJuYW1lNjY2_size_16_color_FFFFFF_t_70]

## 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("未找到该值！")

执行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VzZXJuYW1lNjY2_size_16_color_FFFFFF_t_70 1]

### 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("未找到该值！")

执行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VzZXJuYW1lNjY2_size_16_color_FFFFFF_t_70 2]

--------------------

**往期文章：**

*  [《Python零基础快乐学习之旅》学习笔记2——认识变量与基本数学运算][Python_2]
 *  [《Python零基础快乐学习之旅》学习笔记3——Python的基本数据类型][Python_3_Python]
 *  [《Python零基础快乐学习之旅》学习笔记4——基本输入与输出][Python_4]
 *  [《Python零基础快乐学习之旅》学习笔记5——程序的流程控制使用if语句][Python_5_if]
 *  [《Python零基础快乐学习之旅》学习笔记6——列表（list）][Python_6_list]
 *  [《Python零基础快乐学习之旅》学习笔记7——循环设计][Python_7]
 *  [《Python零基础快乐学习之旅》学习笔记8——元组（tuple）][Python_8_tuple]
 *  [《Python零基础快乐学习之旅》学习笔记9——字典（dict）][Python_9_dict]
 *  [《Python零基础快乐学习之旅》学习笔记10——集合（set）][Python_10_set]
 *  [《Python零基础快乐学习之旅》学习笔记11——函数设计][Python_11]
 *  [《Python零基础快乐学习之旅》学习笔记12——类-面向对象][Python_12_-]
 *  [《Python零基础快乐学习之旅》学习笔记13——模块的设计与应用][Python_13]
 *  [《Python零基础快乐学习之旅》学习笔记14——文档的读取与写入][Python_14]
 *  [《Python零基础快乐学习之旅》学习笔记15——程序调试与异常处理][Python_15]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VzZXJuYW1lNjY2_size_16_color_FFFFFF_t_70]: /images/20221024/9ae6243b67a54e649eb9fe650aec77ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VzZXJuYW1lNjY2_size_16_color_FFFFFF_t_70 1]: /images/20221024/8f7614cd54884926b2b9b16a94179328.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3VzZXJuYW1lNjY2_size_16_color_FFFFFF_t_70 2]: /images/20221024/e358b7f3ba5e4391ad7364135c2c3010.png
[Python_2]: https://blog.csdn.net/username666/article/details/108984204
[Python_3_Python]: https://blog.csdn.net/username666/article/details/108984226
[Python_4]: https://blog.csdn.net/username666/article/details/110963905
[Python_5_if]: https://blog.csdn.net/username666/article/details/111089216
[Python_6_list]: https://blog.csdn.net/username666/article/details/111463110
[Python_7]: https://blog.csdn.net/username666/article/details/113391428
[Python_8_tuple]: https://blog.csdn.net/username666/article/details/113393686
[Python_9_dict]: https://blog.csdn.net/username666/article/details/113436671
[Python_10_set]: https://blog.csdn.net/username666/article/details/113447734
[Python_11]: https://blog.csdn.net/username666/article/details/113482417
[Python_12_-]: https://blog.csdn.net/username666/article/details/113485956
[Python_13]: https://blog.csdn.net/username666/article/details/113509730
[Python_14]: https://blog.csdn.net/username666/article/details/113527356
[Python_15]: https://blog.csdn.net/username666/article/details/113574247