第17课 排序2——其他常见排序算法-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

第五章│数据结构与算法 ——5.3　数据排序，教材P139～146 第17课　排序2——其他常见排序算法 新课程目标 1.理解选择排序的思想，能利用选择排序算法设计程序解决实际问题。　2.理解桶(计数)排序的思想，能利用桶排序算法设计程序解决实际问题。　3.理解插入排序的思想，能利用桶排序算法设计程序解决实际问题。 目录 CONTENTS 教材整体感悟 知本与探源 01 02 命题整体感知 尝试与研析 01 教材整体感悟 知本与探源 教材整体感悟 知本与探源 本课核心点 ● 重难点 1．选择排序 (1)是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小(大)元素，放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。 (2)算法思想 ①初始状态 教材整体感悟 知本与探源 无序区为[0，n－1](共n个元素)，有序区为空。 ②第1趟排序 设置一个变量i，让i从0至n－2循环的同时，对比数组a中元素a[i]与元素a[i＋1]的大小，如果a[i＋1]比a[i]小，则用一个变量k来记住它的位置(即k＝i＋1)。等到循环结束的时候，我们找到了a中最小的元素的位置，然后进行判断。如果这个最小的元素不是a的第一个元素，就让第一个元素和它交换。 ③第i趟排序 教材整体感悟 知本与探源 第i趟排序开始时，当前有序区和无序区分别为[0，i－1]和[i，n－1]。该趟排序从当前无序区中选出最小的元素a[k]，将它与无序区的第1个元素交换。 教材整体感悟 知本与探源 (3)Python程序实现 ①程序代码： a＝[87，77，59，94，46，65] n＝len(a) for i in range(0，n－1)：　　　　　　#排序趟数，n个数排序n－1趟 k＝i for j in range(i＋1，n)： #比较次数，i＝1时，比较n－1次，共n 教材整体感悟 知本与探源 (n－1)/2次 if a[k]>a[j]： #交换次数，最多n(n－1)/2次，可以判断升降序 k＝j if k！＝i： a[i]，a[k]＝a[k]，a[i] print(”第”＋str(i＋1)＋”遍：　”，a) print(”最终结果：　”，a) 教材整体感悟 知本与探源 ②运行结果： 第1遍： [46，77，59，94，87，65] 第2遍： [46，59，77，94，87，65] 第3遍： [46，59，65，94，87，77] 第4遍： [46，59，65，77，87，94] 第5遍： [46，59，65，77，87，94] 最终结果： [46，59，65，77，87，94] 教材整体感悟 知本与探源 ③选择排序的交换操作介于 0 和 (n－1) 次之间，比较次数与数组的初始状态无关，总的比较次数N＝(n－1)＋(n－2)＋…＋1＝n×(n－1)/2。最好情况是序列已经有序，交换0次；最坏情况交换n－1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需的CPU时间比比较所需的CPU时间多，所以n值较小时，选择排序比冒泡排序快。 教材整体感悟 知本与探源 2． 桶(计数)排序 (1)计数排序可以看成是桶排序的一种特殊情况，只是桶的大小粒度不一样。当要排序的 n 个数据所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。 (2)算法思想 ①假设我们用不同大小的小球来表示每一个数组元素的值，我们的目标是使小球从小到大依次排列。 教材整体感悟 知本与探源 ②需要知道最大的球和最小的球分别对应的元素，这里最大的对应8，最小的对应2。 ③我们需要用8－2＋1＝7个计数器来分别统计2到8之间每种小球的个数，图中我们用带有标记的桶来表示。 教材整体感悟 知本与探源 ④遍历所有的小球，将每个值为i的小球放入到第i－1个桶中，比方说第一个小球的值为5，那么我们就把它放到标号为5，也就是从左往右第4个桶中，放入后计数器加1。 教材整体感悟 知本与探源 ⑤我们从左往右依次将每个桶里的小球取出，每取出一个小球，对应桶的计数器减1，直到计数器为 0，将所有桶内的小球都取出后，小球就是从小到大排列了。 教材整体感悟 知本与探源 (3)Python程序实现 ①程序代码： a＝[5，4，2，8，3，7，2，8，3，4，6，6，7，4，5，6] print(”排序前：　”，a) b＝[] m1＝min(a) m2＝max(a) 教材整体感悟 知本与探源 c＝[0]*(m2－m1＋1) for i in range(len(a))： c[a[i]－m1]＋＝1 for i in range(m2－m1＋1)： for j in range(c[i])： b．append(i＋m1) print(”排序后：　”，b) 教材整体感悟 知本与探源 ②运行结果： 排序前： [5，4，2，8，3，7，2，8，3，4，6，6，7，4，5，6] 排序后： [2，2，3，3，4，4，4，5，5，6，6，6，7，7，8，8] 教材整体感悟 知本与探源 3．插入排序 (1)插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个元素插入到已经排好序的有序表中，从而产生一个新的、元素数加1的有序表。在其实现过程使用双层循环，外层循环用于遍历除了第一个元素之外的所有元素，内层循环对当前元素前的有序表进行待插入位置查找，并进行移动。 (2)算法思想 教材整体感悟 知本与探源 从数组的第二个元素开始，将数组中的每一个元素按照(升序或者降序)规则插入到已排好序的数组中以达到排序的目的。一般情况下将数组的第一个元素作为起始元素，从第二个元素开始依次插入。由于要插入到的数组是已经排好序的，所以只要从右向左(或者从后向前)找到插入点插入元素，以此类推，直到将最后一个数组元素插入到数组中，整个排序过程完成。 教材整体感悟 知本与探源 (3)Python程序实现 ①程序代码： a＝[5，4，2，8，3，7，2，8，3，4，6，6，7，4，5，6] print(”排序前：　”，a)  for i in range(1，len(a))： t＝a[i] j＝i－1 教材整体感悟 知本与探源 while j>＝0 and a[j]>t： a[j＋1]＝a[j] j－＝1 a[j＋1]＝t print(”排序后：　”，a) ②运行结果： 排序前： [5，4，2，8，3，7，2，8，3，4，6，6，7，4，5，6] 排序后： [2，2，3，3，4，4，4，5，5，6，6，6，7，7，8，8] 02 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例1有如下Python 程序段： a＝[3，7，8，2，19，10，16，12] n＝len(a) for i in range(2)： k＝i for j in range(i＋1，n)： if a[k]<a[j]： 命题整体感知 尝试与研析 k＝j if i！＝k： a[i]，a[k]＝a[k]，a[i] 下列说法不正确的是(　　) A．执行该程序段后，列表a 中的元素为[19，16，8，2，3，10，7，12] B．代码“for i in range(2)：”等价于“for i in range(0，2)：” C．执行该程序段后，变量k 的值为7 D．将代码“if i！＝k：”修改为“if k>i：”，不会影响程序的运行结果 C 命题整体感知 尝试与研析 【解析】 根据程序结构得知，这是选择排序；根据外层循环得知趟数为2，i值从0开始，则将最大值放到最前面。排序过程为： 第1趟：[19，7，8，2，3，10，16，12] 第2趟：[19，16，8，2，3，10，7，12] 程序段执行后，变量k 的值为6，选项C错误。 命题整体感知 尝试与研析 变式1用数组a 存储一个考场中多个学生考号(编码规则是入学年份4 位＋考场编号2 位＋座位号2 位)和姓名信息，要求按座位号从小到大排序，采用选择排序算法的Python 程序如下： a＝[['20200505'，'张肖明']，['20200501'，'雷海涛']，['20200504'，'傅薇敏']，['20200512'，'胡国强']，['20200526'，'罗晓萍']，['20200503'，'赵建国']] n＝①　　　　　　 for i in range(n－1)： 命题整体感知 尝试与研析 k＝i for j in range(i＋1，n)： p＝a[k][0] q＝a[j][0] if ②　　　　　　： 　　k＝j if k！＝i： 命题整体感知 尝试与研析 a[i]，a[k]＝a[k]，a[i] print(a) 则①、②处填入的代码分别为(　　) A．①len(a)　②p[6：]>q[6：]　　　　　　 B．①len(a)－1　②p[6：]>q[6：] C．①len(a)　②p[7：]>q[7：] D．①len(a)＋1　②p[7：]>q[7：] A 命题整体感知 尝试与研析 【解析】 n个数排序趟数为n－1，由语句“for i in range(n－1)”可知，n为总数，①处为len(a)，选项B和选项D错误；②座位号是最后两位，则可以填入p[6：]>q[6：]，选项A正确。 命题整体感知 尝试与研析 变式2[2023·江山中学检测]某国计划在海岸线上安装雷达探测海上的岛屿。假设海岸线是一条无限的直线，一边是陆地，另一边是海洋。为了找到覆盖所有岛屿所需雷达装置的最小数量，编写程序：输入岛屿数量n、雷达装置的覆盖距离d 以及每个岛屿的位置(由x、y坐标值表示)，若雷达能覆盖所有岛屿，则输出所需雷达的最小数量；否则输出“无法覆盖”。 命题整体感知 尝试与研析 (1)如图所示，海洋中有3个岛屿，位置分别为(1，2)、(－3，1)、(2，1)，若雷达的覆盖距离为2，则至少需要安装2个雷达装置，分别安装在(－2，0)、(1，0)位置上。若上述雷达覆盖距离修改为3，则至少需要安装的雷达装置数为　1　。 (2)实现上述功能的 Python程序如下，请在横线处填入合适的代码。 from math import sqrt n＝int(input(”请输入岛屿的数量n：　”)) d＝int(input(”请输入雷达的半径d：　”)) 命题整体感知 尝试与研析 #qj[i][0]、qj[i][1]分别存储可以覆盖第i个岛屿的雷达能安装的最左边和最右边位置 qj＝[[0，0] for i in range(n)] flag＝True for i in range(n)： x＝int(input(”岛屿坐标x：　”)) y＝int(input(”岛屿坐标y：　”)) 命题整体感知 尝试与研析 if y>d： flag＝False break qj[i][0]＝①　________________________　# qj[i][1]＝x＋sqrt(d*d－y*y) 　print(”无法覆盖”) x－sqrt(d*d－y*y) 命题整体感知 尝试与研析 else： #按左端点升序排序，左端点相同时按右端点升序排序 for i in range(n－1)： k＝i for j in range(i＋1，n)： if ②_____________________________________________________： k＝j qj[k][0]>qj[j][0] or qj[k][0]＝＝qj[j][0] and qj[k][1]> qj[j][1] 命题整体感知 尝试与研析 if k！＝i： qj[k]，qj[i]＝qj[i]，qj[k] num＝1 cur＝qj[0][1] for i in range(1，n)： if cur>qj[i][1]： 　cur＝qj[i][1] 命题整体感知 尝试与研析 elif ③　__________________　： num＋＝1 cur＝qj[i][1] print(”安装的雷达数为：　”，num) (3)若将程序中加框处的代码修改为_______ (单选，填字母)，则不影响程序的正确性。 A．i＝＝n－1　　　　B．i＝＝n　　　　C．i<n　　　　D．y>d cur<qj[i][0] 　D　 命题整体感知 尝试与研析 (4)根据程序可知，对于n个岛屿，在进行排序时最多的交换次数为 ____________。 【解析】 (1)海岸线是一条无限的直线，从题干中2个雷达安装在(－2，0)，(1，0)位置，可见雷达安装在x轴上。雷达的辐射范围为半径为d的圆，圆心的y坐标为0，过岛屿向x轴作一条垂线，构成一个直角三角形，斜边长为d，一条直边为岛屿坐标y，另一条直边在x轴上，长为t，圆的最右边的坐标为x＋t，最左边的为x－t，那么这个圆心就在区间[x－t，x＋t]之间，n个岛屿就有n个区间，至少的雷达数转换为在这些区间的 　n－1　 命题整体感知 尝试与研析 命题整体感知 尝试与研析 例 2有如下Python 程序段： from random import randint a＝[randint(1，10) for i in range(5)] for i in range(1，5)： key＝randint(3，6)*2 j＝i－1 while j>＝0 and key<a[j]： 命题整体感知 尝试与研析 a[j＋1]＝a[j] j－＝1 a[j＋1]＝key 执行该程序段后，列表a的值不可能是(　　) A．[3，6，8，10，12] B．[1，5，8，9，12] C．[6，10，10，12，12] D．[8，9，10，10，12] B 命题整体感知 尝试与研析 【解析】 首先列表a中的初始值是闭区间[1，10]内的5个随机数。key的取值只能是6、8、10、12。while循环会将key插入列表a中的合适位置上，使得列表a的值处于非降序，因此选项A、C、D都是有可能的。特别是选项D中的9，有可能是之前a[0]往后移而来的。而选项B中的9是有可能存在(前面某个元素后移而来)，但是元素5是不可能存在的，只会被key覆盖。故选项B符合题意。 命题整体感知 尝试与研析 变式1以下是实现将正整数序列arr 升序排序的程序段，则横线处可选的代码依次为(　　) arr＝[7，4，2，13，6，5，3，6，17，1] for i in range(1，len(arr))： key＝arr[i] j＝i while (1)　　　　　　：# A 命题整体感知 尝试与研析 arr[j]＝arr[j－1] j－＝1 (2)　　　　　　　# ①j>0 and key<arr[j－1]　②j>＝0 and key<arr[j－1]　③arr[j]＝key　④arr[j－1]＝key A．①③ B．①④ C．②③ D．②④ 命题整体感知 尝试与研析 【解析】 本题中插入排序的思路为将第i 个元素插入至已有序的范围[0，i]，故而需要将a[i]的元素和范围[0，i－1]的元素进行比较，程序中a[i]的值存入key 中，[0，i－1]采用j－1来进行枚举，所以j 的取值最多只能取到1，当j 的值为0 时，不再执行循环，故而第1 空为j>0 and key<arr[j－1]，key 应该插入在arr[j－1]的后一个位置，故而第2 空为arr[j]＝key。 命题整体感知 尝试与研析 变式2某排序算法思想如下：每一趟将一个待排序的数据按其关键字的大小插入到已经排好序的一组数据的适当位置上，直到所有待排序数据全部插入为止。例如(9，3，1，4)升序排序：第一步，将3 插入到有序序列(9)中，得到(3，9)；第二步，将1 插入到有序序列(3，9)中，得到(1，3，9)；第三步，将4 插入到有序序列(1，3，9)中，得到最终有序序列为“1，3，4，9”，如图1所示。编写一个Python程序，先随机生成10个1到100之间的正整数，分别输出排序前和排序后的结果，如图2所示。其代码如下，请在横线处填入合适的代码。 命题整体感知 尝试与研析 import random a＝[0]*10 for i in range(10)： 图1　　　　　　　　 　图2 命题整体感知 尝试与研析 a[i]＝①　______________________________　 print(”排序前：　”，a) for i in range(1，len(a))： t＝a[i] j＝i－1 while j>＝0： if ②　_____________　： 　 random.randint(1，100) a[j]>t 命题整体感知 尝试与研析 a[j＋1]＝a[j] else： break j－＝1 ③　________________　 print(”排序后：　”，a) a[j＋1]＝t 命题整体感知 尝试与研析 【解析】 ①先随机生成10个1到100之间的正整数，答案为random.randint(1，100)。 ②当前j位置的值大于t，则a[j]值后移，答案为a[j]>t。 ③当条件a[j]>t不成立时，执行else后面的语句break，此时的j指向小于或等于t的位置，j的后一位置才是插入的位置，答案为a[j＋1]＝t。 命题整体感知 尝试与研析 例3[2023·丽水中学检测]随机生成n个互不相同的正整数(正整数的最大值不超过m)，并进行排序，排序要求如下：①偶数在前，奇数在后；②奇数降序排序；③偶数升序排序。实现上述功能的部分程序如下，横线处的代码应为(　B　) n＝15；m＝100；a＝[0]*n #本过程产生n个不同的随机整数，n的值在区间[0，m－1]范围内，存储在数组a中，代码略 flag＝[False]*m 命题整体感知 尝试与研析 for i in range(n)： ①　　　　　　＝True for i in range(0，m，2)： if flag[i]： print(②　　　　　　) for i in range(③　　　　　　－1，－2)： if flag[i]： 命题整体感知 尝试与研析 print(i) A．①flag[i]　②i　③m B．①flag[a[i]]　②i　③m－1 C．①flag[a[i]]　②a[i]　③m－1 D．①flag[i]　②a[i]　③m 【解析】 ①利用索引i找到a[i]，a[i]作为列表flag的下标，设置该位置的值为True，填入flag[a[i]]，选项A、D排除； ②for i in range(0，m，2)：中的i是值，直接输出即可，填入i； ③奇数降序排序，填入m－1，选项B正确。 命题整体感知 尝试与研析 变式1某排序算法思想如下：若有11个桶，编号从0～10，随机产生多个整数，每产生一个整数时，就在以该整数为编号的桶中放一面小旗子，最后只要按顺序数出每个桶中有几面小旗子，就能得到这几个整数的有序排列。例如，2号桶中有1面小旗子，表示2出现了一次；3号桶中有1面小旗子，表示3出现了一次；5号桶中有2面小旗子，表示5出现了两次；8号桶中有1面小旗子，表示8出现了一次，按桶的编号顺序读出旗子数量，没有旗子的桶略过，得到有序整数为“2，3，5，5，8”，如图1所示。 命题整体感知 尝试与研析 为此，小李编写了一个Python程序，先随机生成20个5到20之间的正整数，分别输出排序前和排序后的结果，如图2所示。其代码如下，请在横线处填入合适的代码。 import random 图1　　　　　　　　　　　　　　　　　　　　　　图2 命题整体感知 尝试与研析 a＝[0]*20 for i in range(20)： a[i]＝random.randint(5，20) print(”排序前：　”，a) b＝[] m1＝min(a) m2＝max(a) 命题整体感知 尝试与研析 c＝[0]*(①　_____________________) for i in range(len(a))： ②　______________________　 # for i in range(m2－m1＋1)： for j in range(③　________　)： b．append(i＋m1) print(”排序后：　”，b) m2－m1＋1　 c[a[i]－m1]＋＝1 c[i] 命题整体感知 尝试与研析 【解析】 ①定义桶的容量，m2为最大值，m1为最小值，则区间长度为m2－m1＋1。 ②统计出现次数，由于列表c的索引由0开始，需要将a[i]转换为相应位置，并将对应位置的值加1，答案为c[a[i]－m1]＋＝1。 ③按顺序输出实现排序，由于语句“b.append(i＋m1)”存在，直接填入c[i]，若c[i]＝5，则表示i＋m1，连续输出5次。 命题整体感知 尝试与研析 |随|堂|检|测| 1． 有如下Python程序段： for i in range(6)： k＝0 for j in range(1，6)： if not f[j]： if a[j]<a[k] or f[k]： 命题整体感知 尝试与研析 k＝j p[i]＝k＋1 f[k]＝True 数组元素f[0]到f[5]的初始值均为False，数组元素a[0]到a[5]的初始值依次是3，6，4，1，2，5。执行该程序段后，数组元素p[0]到p[5]的值依次是(　　) A．4，5，1，3，6，2 B．4，5，6，1，2，3 C．1，2，3，4，5，6 D．2，6，3，1，5，4 A 命题整体感知 尝试与研析 【解析】 这是选择排序，列表p记下每次查找到的最小值位置(k＋1)。由于比较范围是全部，用列表f标记该位置是否使用。选项A正确。 命题整体感知 尝试与研析 2． 有如下Python程序段： import random a＝[] for i in range(6)： a．append(random.randint(1，5)*2＋i%2) for i in range(1，5)： j＝i；k＝a[j] 命题整体感知 尝试与研析 while a[j－1]<k and j>0： a[j]＝a[j－1]；j＝j－1 a[j]＝k 执行该程序段后，列表a中的值可能是(　　) A．11，8，7，6，5，5 B．8，6，5，5，3，8 C．9，6，7，8，8，11 D．11，11，8，2，2，11 D 命题整体感知 尝试与研析 【解析】 第1个for循环产生随机数，若i为偶数，则产生2～10之间的偶数；若i为奇数，则产生3～11之间的奇数；第2个for循环插入排序，实现降序，注意最后一个元素不参与排序。选项A，奇数有4个，不符合要求，选项错误；选项B，最后一个元素是偶数，不符合要求，选项错误；选项C，没有实现降序排序，选项错误。 命题整体感知 尝试与研析 3．[2023·温岭中学检测]某超市办公用品季度销售数据文件“sales.csv”中包含了商品的类别、产品名称、利润等信息，如图1所示，超市经营者通过分析了解每个商品类别中利润最大的商品，以此作为商品货展安排的依据。为了方便统计设计了一个程序，从电子表格中导入数据至列表，自动统计并输出各商品类别中利润最大的商品，如图2 所示。 命题整体感知 尝试与研析 (1)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 #从CSV 文件读取商品数据存储到列表a 中，并将利润列的数据类型转换为整型，代码略 b＝[ ] n＝len(a) i＝1 #列表a 第0 行为标题，商品数据从第1 行开始 ①　__________　 k＝0 命题整体感知 尝试与研析 while i<n： ②　___________ b．append(a[i][0]) for j in range(i＋1，n)： if a[t][0]＝＝a[j][0] and a[t][2]<a[j][2]： t＝j k＋＝1 t＝i 命题整体感知 尝试与研析 # while i<n and ③　________________　： i＋＝1 print(”办公用品种类数量为：　”＋str(k)) print(”各类别销量最好的商品是：　”) for i in range(1，k＋1)： print(a[i]) a[i][0] in b 命题整体感知 尝试与研析 (2)上述程序中加框处的代码合理的是_______ (单选，填字母)。 A．a[t]，a[i]＝a[i]，a[t] B．a[t]，a[j]＝a[j]，a[t] C．a[t]，a[k]＝a[k]，a[t] D．a[i]，a[k]＝a[k]，a[i] 【解析】 (1)①由最后“办公用品种类数量为：17”输出以及“k＋＝1”分析可得，变量k为计数器，计数器使用时需要初始化，故此处应该为k＝0。 ②由程序代码“if a[t][0]＝＝a[j][0] and a[t][2] < a[j][2]：”可得，t变量 　C　 命题整体感知 尝试与研析 第一次出现，所以②应该填写关于t的表达式，分析可得i为列表a的索引号，for循环的if语句比较的是“a[t][0]与a[j][0]”“a[t][2]与a[j][2]”的关系，故此处应该为t＝i。 ③本处需要填写的是while循环判断条件，循环体为“i＋＝1”，根据分析可得需要执行循环体，除了保证“i<n”之外，还需要保证每一个列表a商品数据中“类别”已经存在于列表b中，故此处应该为a[i][0] in b。 (2)在执行③处while循环之前，外层while循环每循环一次需要交换列表a索引为t、k所对应的数据，故选项C正确。 感谢聆听，再见！ if ： 交集个数。雷达覆盖距离修改为3，则区间分别为[1－，1＋]，[－3－2，－3＋2]，[2－2 ，2＋2]， 这3个区间有共同的交集，则最少需要的雷达数为1。(2)①求每个岛屿最左边的圆心位置。②按左端点升序排序，左端点相同时按右端点升序排序，因此是双关键字排序。③cur表示第1个区间的右端点，若后面的区间右端点比它小，说明两个区间有交集，但要更新两个区间的共同右端点，因此cur的值为最左边的qj[i][1]，如区间[1，4]，[2，3]有交集[2，3]。若后面的区间左端点qj[i][0]比交集的右端点小，表示两个区间相离，需要一个新的雷达，如区间[1，4]和[5，6]就没有交集。(3)当y>d时，flag的值为False，表示雷达不能覆盖。(4)对于n个岛屿最多排序n－1趟。 $$