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

专题十八 常考排序算法解析 一、单项选择题 1.在每一轮中插入排序（ ）。 A. 选择最小值并放到前面 B. 交换相邻元素 C. 将一个元素插入到已排序序列的正确位置 D. 将列表分成两部分，分别排序后再合并 2. 二分查找法的前提条件是（ ）。 A. 查找的数组必须是无序的 B. 查找的数组必须是升序排列的 C. 查找的数组必须是降序排列的 D. 查找的数组可以是任意顺序的 3. 选择排序的主要特点是（ ）。 A. 每一轮选择最小值并放到已排序部分的末尾 B. 每一轮将一个元素插入到已排序序列中 C. 通过交换相邻元素逐步排序 D. 将列表分成两部分，分别排序后再合并 4. 冒泡排序的基本思想是（ ）。 A. 通过交换相邻元素，将最大的元素逐步移到列表末尾 B. 通过选择最小值，将其放到列表的前面 C. 将一个元素插入到已排序的序列中 D. 将列表分成两部分，分别排序后再合并 5. 以下是通过不断地将一个元素插入到已排序序列中来构建整个有序序列的算法排序是（ ）。 A. 冒泡排序 B. 选择排序 C. 插入排序 D. 快速排序 二、程序分析题 1.下面是使用选择排序算法来升序排序列表，请补全空缺的代码 lst=[7,3,1,5,4,6,2] n=len(lst) for i in range(n-1): minIndex=i for j in range(i+1,n): if ____①____: minIndex=j ________②__________ print(lst) ①____________ ②_______________ 2.下面是使用插入排序算法来升序排序列表，请补全空缺的代码 lst=[17,13, 11, 4, 3] n=len(lst) for i in range(1,n): for j in range(___①___,___②___,-1): if ____③___: lst[j] , lst[j + 1] =lst[j+1],lst[j] print(lst) ①____________ ②_______________ ③_______________ 3.下面是使用冒泡排序算法来降序排序列表，请补全空缺的代码 lst=[15,13,11,19,12,18,14,17,16] n=len(lst) for i in range(n-1): for j in range(___①___): if ___②___: lst[j],lst[j+1]=lst[j+1],lst[j] print(lst) ①____________ ②_______________ 三、程序设计题 1.随机生成10个1-100之间的偶数，然后使用冒泡排序算法来升序排序。（冒泡排序用函数封装）。 2.已知列表lst=[3,1,4,2,1,3,5,9,6,2,8]，对列表去重的同时要保持元素原来的相对位置。如元素1在元素4的前面。再使用选择排序算法降序排序。 3.随机生成10个1-100之间的奇数，然后使用插入排序算法来升序排序。（插入排序用函数封装）。 4.已知列表lst=[5,4,7,3,9,6,8,11,10]，列表的每个元素加6再与10取余来替换该元素。若目标数为5，使用二分查找法查找目标数是否在列表里面，若在返回数字的位置，若不在则返回-1。 学科网（北京）股份有限公司 $$ 专题十八 常考排序算法解析 一、单项选择题 1.在每一轮中插入排序（ ）。 A. 选择最小值并放到前面 B. 交换相邻元素 C. 将一个元素插入到已排序序列的正确位置 D. 将列表分成两部分，分别排序后再合并 【答案】C 【解析】插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。 2. 二分查找法的前提条件是（ ）。 A. 查找的数组必须是无序的 B. 查找的数组必须是升序排列的 C. 查找的数组必须是降序排列的 D. 查找的数组可以是任意顺序的 【答案】B 【解析】二分查找法要求数组是有序的，通常是升序排列。 3. 选择排序的主要特点是（ ）。 A. 每一轮选择最小值并放到已排序部分的末尾 B. 每一轮将一个元素插入到已排序序列中 C. 通过交换相邻元素逐步排序 D. 将列表分成两部分，分别排序后再合并 【答案】A 【解析】选择排序的核心思想是每一轮从未排序部分选择最小值，并将其放到已排序部分的末尾。 4. 冒泡排序的基本思想是（ ）。 A. 通过交换相邻元素，将最大的元素逐步移到列表末尾 B. 通过选择最小值，将其放到列表的前面 C. 将一个元素插入到已排序的序列中 D. 将列表分成两部分，分别排序后再合并 【答案】A 【解析】冒泡排序通过多轮比较和交换相邻元素，将较大的元素逐步移到列表的末尾。 5. 以下是通过不断地将一个元素插入到已排序序列中来构建整个有序序列的算法排序是（ ）。 A. 冒泡排序 B. 选择排序 C. 插入排序 D. 快速排序 【答案】C 【解析】插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。 二、程序分析题 1.下面是使用选择排序算法来升序排序列表，请补全空缺的代码 lst=[7,3,1,5,4,6,2] n=len(lst) for i in range(n-1): minIndex=i for j in range(i+1,n): if ____①____: minIndex=j ________②__________ print(lst) ①____________ ②_______________ 【答案】 ① lst[minIndex]>lst[j] ② lst[i],lst[minIndex]=lst[minIndex],lst[i] 【解析】选择排序的核心思想是每一轮从未排序部分选择最小值，并将其放到已排序部分的末尾。 2.下面是使用插入排序算法来升序排序列表，请补全空缺的代码 lst=[17,13, 11, 4, 3] n=len(lst) for i in range(1,n): for j in range(___①___,___②___,-1): if ____③___: lst[j] , lst[j + 1] =lst[j+1],lst[j] print(lst) ①____________ ②_______________ ③_______________ 【答案】 ① i-1 ② -1 ③ lst[j]>lst[j+1] 【解析】插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。 3.下面是使用冒泡排序算法来降序排序列表，请补全空缺的代码 lst=[15,13,11,19,12,18,14,17,16] n=len(lst) for i in range(n-1): for j in range(___①___): if ___②___: lst[j],lst[j+1]=lst[j+1],lst[j] print(lst) ①____________ ②_______________ 【答案】 ① n-1-I ② lst[j]<lst[j+1] 【解析】冒泡排序通过多轮比较和交换相邻元素。由于是降序排序，因此将较大的元素逐步移到列表的头部。 三、程序设计题 1.随机生成10个1-100之间的偶数，然后使用冒泡排序算法来升序排序。（冒泡排序用函数封装）。 【答案】 import random lst=[random.randrange(2,100,2) for i in range(10)] def bubble(arr): n=len(arr) for i in range(n-1): for j in range(n-1-i): if arr[j]>arr[j+1]: arr[j],arr[j+1]=arr[j+1],arr[j] return arr print(bubble(lst)) 【解析】 1. 随机生成偶数： · 可以使用列表推导式 · 使用 random.randrange(2,100,2) 生成随机偶数。 · 循环直到生成指定数量的偶数。 2. 冒泡排序算法： · 外层循环控制排序的轮数，从 i=0 到 i=n-2。 · 内层循环在每一轮中比较相邻元素并进行交换，范围从 j=0 到 j=n-2-i。 · 如果前一个元素大于后一个元素，则交换它们的位置。 3. 封装函数： · bubble函数负责对列表进行冒泡排序。 2.已知列表lst=[3,1,4,2,1,3,5,9,6,2,8]，对列表去重的同时要保持元素原来的相对位置。如元素1在元素4的前面。再使用选择排序算法降序排序。 【答案】 lst=[3,1,4,2,1,3,5,9,6,2,8] nlst=[] for i in lst: if i not in nlst: nlst.append(i) n=len(nlst) for i in range(n-1): Ind=i for j in range(i+1,n): if nlst[Ind]<nlst[j]: Ind=j nlst[i],nlst[Ind]=nlst[Ind],nlst[i] print(nlst) 【解析】 1. 去重并保持相对位置： · 创建一个新列表nlst，遍历原始列表， · 如果当前元素不在nlst中，并将该元素加入nlst。 · 这样可以确保每个元素只保留第一次出现的位置，同时保持相对顺序。 2. 选择排序降序排序： · 外层循环控制排序的轮数，从 i=0 到 i=n-2。 · 内层循环在每一轮中从未排序部分找到最大值的索引 max_index。 · 将最大值与当前轮次的第一个未排序元素交换位置。 · 通过这种方式，每一轮都将最大值放到已排序部分的末尾，最终实现降序排序。 3.随机生成10个1-100之间的奇数，然后使用插入排序算法来升序排序。（插入排序用函数封装）。 【答案】 import random lst=[random.randrange(1,100,2) for i in range(10)] def cr(arr): n=len(arr) for i in range(1,n): for j in range(i-1,-1,-1): if arr[j]>arr[j+1]: arr[j] , arr[j + 1] = arr[j+1],arr[j] return arr print(cr(lst)) 【解析】 1. 随机生成奇数： · 使用 random.randrange(1,100,2) 生成随机奇数。 · 循环直到生成指定数量的奇数。 2. 插入排序算法： · 外层循环从 i=1 到 i=n-1，表示将第 i 个元素插入到前面的有序序列中。 · 内层循环从 j=i-1 开始，将arr[i] 与前面的元素进行比较，如果前面的元素大于arr[i]，则将前面的元素向后移动一位。 · 找到合适的位置后，将arr[i] 插入到该位置。 3. 封装函数： · cr函数负责对列表进行插入排序。 4. 主程序流程： · 调用cr函数对列表进行排序。 · 打印排序后的列表。 4.已知列表lst=[5,4,7,3,9,6,8,11,10]，列表的每个元素加6再与10取余来替换该元素。若目标数为5，使用二分查找法查找目标数是否在列表里面，若在返回数字的位置，若不在则返回-1。 【答案】 lst=[5,4,7,3,9,6,8,11,10] lst = [(x + 6) % 10 for x in lst] 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) 【解析】 1.列表元素操作： 使用列表推导式对每个元素进行操作： lst = [(x + 6) % 10 for x in lst] 这里的操作是将每个元素加6后对10取余 2.排序： 使用 sort() 方法对转换后的列表进行升序排序，以便后续使用二分查找法。 3.二分查找法： 初始化两个指针st和ed，分别指向列表的起始和末尾位置。 在循环中计算中间位置 mid，比较lst[mid] 和目标值 target： 如果相等，返回 mid。 如果 lst[mid] 小于 target，说明目标值在右半部分，调整 st 指针为 mid + 1。 如果 lst[mid] 大于 target，说明目标值在左半部分，调整 ed 指针为 mid - 1。 如果循环结束仍未找到目标值，返回-1。 学科网（北京）股份有限公司 $$