专题十八 常考排序算法解析（课件）-《Python程序设计》职教高考备考讲练测（安徽省）

专题十八 常考排序算法解析 Python程序设计 1 考纲解读 一 1.掌握冒泡排序算法 2.掌握选择排序算法 3.掌握插入排序算法 4.掌握二分(折半)查找法 冒泡排序 3 知识点梳理-描述-基本思路 二 描述 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，依次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。 基本思路 冒泡排序的基本思想是通过对数组中的元素进行两两比较和交换，使得每一轮最大的元素被放置到正确的位置上。具体步骤如下： 比较相邻元素：从数组的第一个元素开始，比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置。 重复比较和交换：继续比较下一对相邻元素，重复上述步骤，直到比较到数组的末尾。 知识点梳理-算法描述-算法动画 二 假设有一个列表 lst，长度为 n，冒泡排序的详细步骤如下： 外层循环：控制排序的轮数，从 i=0 到 i=n-1。 内层循环：在每一轮中，比较相邻的两个元素并进行交换，从 j=0 到 j=n-i-1。 交换元素：如果 lst[j] > lst[j+1]，则交换这两个元素的位置。 知识点梳理-代码实现 二 lst=[5,3,1,9,2,8,4,7,6] n=len(lst) for i in range(n-1): for j in range(n-1-i): if lst[j]>lst[j+1]: lst[j],lst[j+1]=lst[j+1],lst[j] print(lst) 插入排序 7 知识点梳理-描述-基本思路 二 描述 插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 基本思路 插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。具体步骤如下： 从第一个元素开始：默认第一个元素已排序。 取出下一个元素：在已排序的序列中从后向前扫描。 比较和移动：如果该元素（已排序）大于新元素，将该元素移到下一位置。 重复步骤3：直到找到已排序的元素小于或等于新元素的位置。 插入新元素：将新元素插入到该位置后。 重复步骤2-5：直到所有元素均排序完成。 知识点梳理-算法描述和动画演示 二 假设有一个列表lst，长度为 n，插入排序的详细步骤如下： 外层循环：从 i=1 到 i=n-1，表示将第 i 个元素插入到前面的有序序列中。 内层循环：从 j=i-1 开始，将 lst[i] 与前面的元素进行比较，如果前面的元素大于lst[i]，则将前面的元素向后移动一位。 插入元素：找到合适的位置后，将 lst[i] 插入到该位置。 知识点梳理-代码实现 二 lst=[12, 11, 13, 5, 6] n=len(lst) for i in range(1,n): for j in range(i-1,-1,-1): if lst[j]>lst[j+1]: lst[j] , lst[j + 1] =lst[j+1],lst[j] print(lst) 知识点梳理-详细过程 二 详细过程： 初始状态：[12, 11, 13, 5, 6] 第一轮（i=1，key=11）： 比较 11 和 12，11 小于 12，将 12 向后移动一位，得到 [12, 12, 13, 5, 6] 将 11 插入到位置 0，得到 [11, 12, 13, 5, 6] 第二轮（i=2，key=13）： 比较 13 和 12，13 大于 12，直接插入到位置 2，得到 [11, 12, 13, 5, 6] 第三轮（i=3，key=5）： 比较 5 和 13，5 小于 13，将 13 向后移动一位 比较 5 和 12，5 小于 12，将 12 向后移动一位 比较 5 和 11，5 小于 11，将 11 向后移动一位 将 5 插入到位置 0，得到 [5, 11, 12, 13, 6] 第四轮（i=4，key=6）： 比较 6 和 13，6 小于 13，将 13 向后移动一位 比较 6 和 12，6 小于 12，将 12 向后移动一位 比较 6 和 11，6 小于 11，将 11 向后移动一位 将 6 插入到位置 1，得到 [5, 6, 11, 12, 13] 选择排序 12 知识点梳理-描述-基本思路 二 描述 选择排序是一种简单直观的排序算法，它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完为止。选择排序是不稳定的排序方法。 基本思路 选择排序的主要思想是通过不断地选择剩余元素中的最小值（或最大值），并将其放到已排序序列的末尾。具体步骤如下： 初始状态：待排序的数组。 选择最小值：从数组中找到最小值（或最大值），记录其索引。 交换位置：将最小值与数组中第一个未排序的元素交换位置。 缩小范围：将剩余的未排序部分视为新的数组，重复步骤2和3，直到所有元素排序完成。 知识点梳理-算法描述-算法动画 二 算法描述 假设有一个数组 lst，长度为 n，选择排序的详细步骤如下： 外层循环：控制排序的轮数，从 i=0 到 i=n-1。 内层循环：在每一轮中，从 j=i+1 到 j=n-1，找到最小值的索引。 比较和更新最小值索引：如果当前元素小于当前最小值，则更新最小值的索引。 交换元素：将最小值与当前轮次的第一个未排序元素交换位置。 知识点梳理-代码实现 二 lst=[64, 25, 12, 22, 11] n=len(lst) for i in range(n-1): minIndex=i for j in range(i+1,n): if lst[minIndex]>lst[j]: minIndex=j lst[i],lst[minIndex]=lst[minIndex],lst[i] print(lst) 知识点梳理-详细过程 二 选择排序的详细过程： 初始状态：[64, 25, 12, 22, 11] 第一轮： 找到最小值 11，索引为 4 交换 64 和 11，得到 [11, 25, 12, 22, 64] 第二轮： 在子数组 [25, 12, 22, 64] 中找到最小值 12，索引为 2 交换 25 和 12，得到 [11, 12, 25, 22, 64] 第三轮： 在子数组 [25, 22, 64] 中找到最小值 22，索引为 3 交换 25 和 22，得到 [11, 12, 22, 25, 64] 第四轮： 在子数组 [25, 64] 中找到最小值 25，索引为 3 无需交换，数组已经有序 二分（折半）查找法 17 知识点梳理-描述-基本思路 二 描述 二分查找法是一种高效的查找算法，它通过不断将查找区间分成两部分，逐步缩小查找范围，直到找到目标值或确定其不存在。二分查找法要求查找的数组是有序的（通常是升序或降序）。 基本思路 假设我们有一个升序排列的数组 lst，要查找的目标值为 target。二分查找法的基本思想如下： 初始化：设置两个指针，low 指向数组的起始位置（索引0），high 指向数组的末尾位置（索引n-1，其中n是数组长度）。 循环查找：在查找过程中，计算中间位置 mid，比较 lst[mid] 和 target 的大小： 如果 lst[mid] 等于 target，则查找成功，返回 mid。 如果 lst[mid] 小于 target，则说明目标值在数组的右半部分，调整 low 指针为 mid + 1。 如果 lst[mid] 大于 target，则说明目标值在数组的左半部分，调整 high 指针为 mid - 1。 终止条件：当 low 大于 high 时，说明数组中不存在目标值，返回-1。 知识点梳理-算法描述-算法动画 二 算法描述 初始化指针：low = 0，high = len(arr) - 1。 进入循环：当 low <= high 时，执行以下步骤： 计算中间位置：mid = (low + high) // 2。 比较 arr[mid] 和 target： 如果相等，返回 mid。 如果 arr[mid] < target，则 low = mid + 1。 如果 arr[mid] > target，则 high = mid - 1。 查找失败：如果循环结束仍未找到目标值，返回-1。 知识点梳理-代码实现 二 lst=[1,3,4,5,8,16,24,56,78] target=78 st=0 ed=len(lst)-1 count=0 # 查找次数 while count<=len(lst): mid=(st+ed)//2 if target==lst[mid]: print("目标数字位置:",mid) break elif target<lst[mid]: ed=mid-1 else: st=mid+1 count+=1 else: print(-1) 注意:若列表lst里面的元素是乱序的，则需要升序排序好。 限时练习 三 1.以下代码实现了哪种排序算法？ lst = [64, 25, 12, 22, 11] n = len(lst) for i in range(n-1): minIndex = i for j in range(i+1, n): if lst[minIndex] > lst[j]: minIndex = j lst[i], lst[minIndex] = lst[minIndex], lst[i] print(lst) A. 冒泡排序 B. 插入排序 C. 选择排序 D. 快速排序 【答案】C 【解析】代码中有一个外层循环控制轮数，内层循环在每轮中找到最小值的索引，并与当前轮次的第一个未排序元素交换位置，这是选择排序的典型实现方式。 限时练习 三 2.已知lst=[7,1,5,2,3,9,4]，使用冒泡排序对列表进行升序排序 【答案】 lst=[7,1,5,2,3,9,4] n=len(lst) for i in range(n-1): for j in range(n-1-i): if lst[j]>lst[j+1]: lst[j],lst[j+1]=lst[j+1],lst[j] print(lst) 【解析】冒泡排序通过多轮比较和交换相邻元素，将较大的元素逐步移到列表的末尾 限时练习 三 3.已知lst=[7,1,5,2,3,9,4]，使用选择排序对列表进行升序排序 【答案】 lst=[7,1,5,2,3,9,4] n=len(lst) for i in range(n-1): minIndex=i for j in range(i+1,n): if lst[minIndex]>lst[j]: minIndex=j lst[i],lst[minIndex]=lst[minIndex],lst[i] print(lst) 【解析】选择排序的核心思想是每一轮从未排序的部分找到最小值，并将其放到已排序部分的末尾 限时练习 三 4.已知lst=[7,1,5,2,3,9,4]，使用插入排序对列表进行升序排序 【答案】 lst=[7,1,5,2,3,9,4] n=len(lst) for i in range(1,n): for j in range(i-1,-1,-1): if lst[j]>lst[j+1]: lst[j] , lst[j + 1] =lst[j+1],lst[j] print(lst) 【解析】插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。 限时练习 三 5.已知lst=[7,1,5,2,3,9,4]查找目标数字5，返回目标数字的位置 【答案】 lst=[7,1,5,2,3,9,4] lst.sort() target=5 st=0 ed=len(lst)-1 count=0 # 查找次数 while count<=len(lst): mid=(st+ed)//2 if target==lst[mid]: print("目标数字位置:",mid) break elif target<lst[mid]: ed=mid-1 else: st=mid+1 count+=1 else: print(-1) 【解析】二分查找是一种高效的查找算法，但要求列表必须是有序的。因此，在使用二分查找之前，需要先对列表进行排序 归纳小结 四 谢谢观看 27 $$