5.3 数据排序（教学设计）信息技术浙教版2019选择性必修1

5.3 数据排序（教学设计） 年级 高二年级 授课时间 2课时 课题 5.3 数据排序 教学 目标 1.了解排序的主要作用，掌握排序的基本概念，知道常用的排序算法。 2.熟练掌握冒泡排序的基本思想和基本程序结构，并能够编程实现冒泡排序。 3.能够完整地进行抽象与建模、设计算法与数据结构、程序实现，解决排序算法的应用问题。 教学 重难点 重点： 1.结合实际项目，掌握用计算机解决问题的一般过程。 2.学会根据项目特点，提炼恰当的数据结构。 3.理解冒泡排序中的迭代思想。 难点： 1.排序算法中对复杂数据结构的处理。 教学 准备 多媒体课件、多媒体教室 教学过程 教师活动 学生活动 新 课 导 入 一、课堂导入 1.通过几张图片展示：上图中都是生活中常见的一些排队或者可以说是排序。抛出问题：我们在日常生活中会经常经历排序的场景，比如体育课上按身高排列等等熟悉的生活体验。这种熟悉的经验，在计算机中的排序又有哪些? 同学们对于电脑并不陌生，在计算机软件系统中，排序是一种常见的操作。 如文件夹中图片文件可分别按名称、大小、类型、修改日期等方式进行排序；电子邮件列表一般按照日期排序，最新的邮件被放置在最顶端；购物网站上搜索到的某类商品可按价格、销量、信用等方式进行排序。 从学生熟悉的事物出发，引出本节课的项目，吸引学生的学习兴趣，培养学生用计算机解决实际问题的信息意识。 新 知 讲 授 一、排序 1.概念 将无序数据按照某种规则(递增或递减)，重新排列使其变成有序数据。 对一次具体排序而言，总是针对某一组数据元素的某种具体的序关系进行操作。 2.未排序数据的存储方式 ①以数组作为存储结构 通过关键字之间的比较判断，将数据移到合适的位置 ②以链表作为存储结构 对链表进行排序无须移动数据，只需修改指针即可 计算机要对数据排序，先要考虑数据的组织形式。如果有一组数(23，20，13，18，14，11)分别存储以数组、链表的形式，排序有什么不同呢? 数据存储情况 为了分析问题方便，我们以后假设数据以数组形式存储，然后讨论它的排序算法。排序的基本要求是什么? 以数组为例，每个数组元素都对应存储一个数据。 例如，存储在数组元素d[0]中的数据是23，d[1]中存储的是20，等等。 如果对数组d中的6个数据按升序进行排序，即调整数组d中所有数据的存储位置，使最小的数据存储在d[0]中，次小的数据存储在d[1]中……最大的数据存储在d[5]中。数组d中的所有数据满足：d[0]≤d[1]≤d[2]≤d[3]≤d[4]≤d[5]。这里两个数组元素的比较：d[i]≤d[j] (i=0,1,…,5; j=0,1,…,5)，指的是d[i]中的数据小于或等于d[j]中的数据。 对数组d按升序进行排序后，数据的存储情况如下图所示： 排序后的数据存储情况 3.总结 排序(sorting)就是整理数据的序列，使其中元素按照某个值的递增(或递减)的次序重新排列的操作。在排序的过程中，序列里的数据元素的值保持不变，但其排列顺序可能改变。 4.探讨与讨论 ①对“842715”中的数字进行选择排序中的两遍“加工”即为某密码锁 的密码，则该密码可能是( ) A.842715 B.142785 C.872415 D.124578 ②对下列一组原始数组:13，15，2，11，8，18进行选择排序，第一趟排序介绍，数组的状态不可能是（ ） A.2，15，13，11，8，18 B.18，15，2，11，8，13 C.13，15，2，11，18，8 D.13，15，18，11，8，2 二、常见的排序算法 1.拓展链接：Python中的排序函数 Python中，对列表进行排序的方法有两种：一种是列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列；另外一种是内建函数sorted方法，返回一个新的序列，而原来的序列依然存在。 2.导入 在一次电视节目上,谷歌总裁施密特提出问题:“如何才能更有效地对一百万个32位长整数进行排序?”同在现场的奥巴马总统立刻响应道:“肯定不能用冒泡排序法。”施密特评价说:"天哪!他是从谁那里听说这个的。” 提问：这里奥巴马总统提到的“冒泡排序”，它是如何进行的呢? 3.概念 冒泡排序（Bubble Sort）是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 （1）以升序为例 ①第一遍加工 冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，对相邻两个数进行比较，将较小的数据换到上面的一个元素中（或将较大的数据换到下面的一个元素中）。重复这一过程，直到处理完最后两个元素中的数据，称为一遍加工。 当第一遍加工完成时，数 据 结 构与算法最小的数据已经“上浮”到第一个元素的位置（或最大的数据“下沉”到最后一个元素的位置）。然后对余下的n–1个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。由于每一遍加工都是将本遍最小的元素像气泡一样“上浮”至本遍的顶端位置（或将本遍最大的元素“下沉”至本遍的底端位置），故称为冒泡排序。 冒泡排序算法对数组d的第一遍加工过程 第一遍加工完毕，最大值23“下沉”至数组最后一个元素的位置。即第一遍加工，先比较相邻两元素d[0]与d[1]，不符合所要求的顺序，则交换两者的位置；再比较调整d[1]与d[2]……最后比较调整d[4]与d[5]。 ②第二遍加工 第二轮排序时，只排到导数第二个...以此排完。 若要排序的数有n个，则需要n–1遍加工。第i遍加工中，从第一个数开始，相邻两数比较，若反序则交换两者的位置，直到第n+1–i个数为止。第一个数与第二个数比较，第二个数与第三个数比较……第n–i个与第n+1–i个比较，共比较n–i次。此时第n+1–i个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。 对n个元素的数组，用冒泡排序算法进行排序时，共需比较： 其时间复杂度为〇(n 2 )。 排序过程中，按右面的方式使用变量i和j 变量i：记录正进行的处理遍数，第1遍处理时值为1，第2遍处理时值为2，以此类推。 变量j：记录当前数组元素的下标。每遍处理过程中，j值总是从第一个数组元素的下标值0开始，按每次加1的方式，直至j=n–i–1为止。每当j取定一个值后，当前数组元素d[j]将与它的后一个元素d[j+1]进行比较，若d[j] ＞d[j+1]，则互换这两个数组元素 中的数据。 冒泡排序算法对数组d的5遍加工过程 对规模为n的数组d，冒泡排序的算法流程图如下图所示。 冒泡排序的算法流程图 （2）代码实现： def bubble_sort(d): length=len(d) #序列长度为length，需要执行length–1遍加工 for i in range(1,length): for j in range(0,length–i): if d[j]>d[j+1]: temp=d[j] d[j]=d[j+1] d[j+1]=temp （3）在选取排序算法时，可以根据待排序数据自身的特点来选择相应的算法。 4.探讨与讨论 （1）某场篮球联赛中，有5个班级的比赛积分依次为14,11,13,8,9。若 采用冒泡排序算法从右到左对其进行升序排序，则第二轮排序后的结果是 ( ) A.8,11,13,14,9 B.8,9,13,14,11 C.8,9,14,11,13 D. 14,13,11,9,8 （2）某 Python程序如下： a=[3,1,9,7,6,3] n=len(a) for i in range(1,n): for j in range(n-2,i-2,- 1): if a[jka[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序运行后，数组a的值是（ ） A.[9,3,1,7,6,3] B.[9,7,6,3,3,1] C.[1,3,3,9,7,6] D.[1,3,3,6,7,9] 三、排序算法的应用 1.课堂引入 教师抛出问题：同学们，这本书和字典你们都认识吗？都使用过，你们在使用字典或翻书的时候，都是按照其中的顺序进行查找的。 排序能使数据有序，而有序的数据更加便于使用。 2.排序算法在实际生活中的应用 （1）奥运成绩排行榜 每届奥运会各大媒体都会公布一个成绩排行榜，但每个排行榜可能略有不同，如有的是按金牌总数排列的“金牌榜”，有的是按奖牌总数排列的“奖牌榜”，甚至还有“国民人均奖牌榜”，等等。现在，以2008年北京奥运会的奖牌数为例，部分数据（数据统计时间为2008年8月25日）。请你编写一个程序，编制金牌排行榜。 2008年北京奥运会奖牌数表 ①抽象与建模 从表中的数据可以看出，每个国家的信息是一条记录，包括编号、国家/地区、人口数量、各奖牌数等数据项。编制金牌排行榜，要按排序关键字“金牌”降序排序。排序过程中若要交换，则要将待交换的两条记录整体进行交换。 ②设计算法与数据结构 第一种方案： 采用7个一维数组按列存储，即每个数组分别存储每个国家的编号、国家/地区、人口数量、各奖牌数等，如定义b数组存储表中8个国家的金牌数量，其对应的值为[51,1,36,1,3,0,23,9] ； 第二种方案： 采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如[8,"中国",136407,51,21,28,100]对应中国的相关信息。 采用不同的存储方式，排序时数据的交换方式也有不同： ※若采用7个一维数组按列存储，排序过程中，两条记录的对应数据项都要相应交换，即要考虑7个一维数组的操作。 ※若采用1个一维数组按行存储，排序中的数据交换可对整条记录进行交换操作。 ③编写程序 若存储结构采用1个一维数组，以金牌数为关键字进行降序排序，程序如下： 程序中的“a[j][3]”表示某条记录索引位置为3的信息，即某个国家的金牌数。而“a[j]=a[j+1]”表示整条记录的所有信息的赋值。 3.探讨与讨论 ①有如下Python 程序段: A=[15,20,11,6,12,8,7,3] for i in range(1,3): for j in range(0,8-i): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序段运行后,数组a中的数据依次为（ ） A.3,6,7.8.11.12.15,20 B15,11.6,12,8,7.3,20 C.11,6,12,8.7,3,15,20 D.6,11,8.7.3.12.15.20 四、课堂小练 五、小结 1.排序 (1)概念 (2)存储方式 数组、链表 2.常见的排序算法 (1)拓展链接：Python中的排序函数 列表自带的sort方法、内建函数sorted方法 (2)冒泡排序 ①概念 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 3.排序算法的应用 尽管学生对排序并不陌生， 但如何严谨地定义排序，并 与数据在计算机中存储形式 结合起来思考问题，还需要进一步清晰化。 通过未排序数据的存储方式，串起排序的作用与意义、数据排序的组织形式、排序的概念与要求等等。 通过实际问题，恰当地选择排序结构，并总结排序的概念和特性。(意图:体现先学后教的理念。） 通过课堂练习，加深同学们对数据排序的理解。 通过延伸：拓展链接，将Python中的排序函数问题进行抽象化的展示，让学生理解Python中的排序函数如何解决实际中的问题，体验用Python中的排序函数解决问题的基本流程，逐步形成运用Python中的排序函数解决问题的思维方式和学科方法。 通过有趣的故事，涉及术语 “冒泡排序”,激起学生对排 序的兴趣，对排序概念形成初步认识，同时对“冒泡排序”是什么产生强烈好奇心。 按照由粗到细、逐步求精的策略,推动学生加深对冒泡排序的深刻认识。 从第一遍加工的实现中可以发现规律,进而引导学生概括出全部算法过程。 从第二遍加工的实现中再次加深这个规律的理解,进而引导学生概括出全部算法过程。 通过实际问题，恰当地选择迭代结构，并总结迭代的基本操作。 从前面的两次加工工程，提炼出最红的5遍加工过程，循序渐进，最终得出冒泡算法的算法流程图，然后再引导学生写出代码。 展示多个排序算法，然后纵向对比出各个算法的特点，让学生一目了然。 通过课堂练习，加深同学们对冒泡算法的理解。 从学生熟悉的事物出发，引出本节课的项目，吸引学生的学习兴趣，培养学生用计算机解决实际问题的信息意识。 通过排序算法在实际生活中的应用为例子，体会排序过程中若要发生交换，则要将待排序的两记录整体进行交换。 引导学生思考复杂数据排序应当注意的事项。 引导学生总结不同数据存储形式，带来的数 据交换形式不同。 在设计算法与数据结构以两种方案对比的方式展示出来，让学生在对比中更好的理解排序算法在生活中的应用。 通过案例讲解，体验排序算法在生活中的应用，逐步形成运用排序思想解决问题的思维方式和学科方法。 通过课堂练习，加深同学们对排序算法的理解。 用练习巩固课堂知识，帮助学生更好地掌握。 课 堂 练 习 （有题有答案有解析） 1.排序是将无序数据按照某种规则(递增或递减)，重新排列使其变成 。 2.待排序数据的存储方式一般有两种： 、 。 3.在排序的过程中，序列里的数据元素的值 ，但其排列顺序 。 4.Python中，对列表进行排序的方法有两种：一种是 ，只适用于列表；另外一种是 。 5.冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数 ，较小的数 的一种排序技术。 6.常见的排序算法有： 、 、 、 、 、 等。 7.某场篮球联赛中，有5个班级的比赛积分依次为14,11,13,8,9。若 采用冒泡排序算法从右到左对其进行升序排序，则第二轮排序后的结果是 ( ) A.8,11,13,14,9 B.8,9,13,14,11 C.8,9,14,11,13 D. 14,13,11,9,8 8.篮球联赛中，有5个班级的比赛积分依次为14，11，13，8，9.若采用冒泡排序算法对其进行从大到小排序，需要排几遍交换几次（） A.1 2 B.4 2 C.1 8 D.4 8 9.采用冒泡排序算法对数据序列18,13,15,2,1,20进行排序，第一轮排序后的结果为20,18,13,15,2,1,则完成整个序列的排序需要进行数据交换的次数总共是( ) A.6 B.7 C.8 D.9 10.采用冒泡排序算法对数据序列“7，3，8，2，1，9”进行排序，第一轮排序后的结果为“3，7，2，1，8，9”则完成整个排序需要交换的次数是() A.6次 B.7次 C.8次 D.9次 11.下列关于冒泡排序的叙述，正确的是() A.10个数冒泡排序每一趟都要进行9次数据比较 B.冒泡排序相邻的数据一定要比较并交换 C.冒泡排序相邻的数据一定要比较，但不一定交换 D.冒泡排序是所有排序算法最快的一种算法 参考答案： 1.有序数据 2.数组、链表 3.保持不变、可能改变 4.列表自带的sort方法、内建函数sorted方法 5.下沉（上冒）、上冒（下沉） 6.选择排序、插入排序、快速排序、堆排序、归并排序、桶排序 7.答案：C [解析]据题意:该数组进行从小到大排序第1种情况:从数组第1个到最后一个元素向后 走访数组，进行数据比较，则: 第一趟:14与11比较并交换，14与13比较并交换，14与8比较并交换，14与9比较并交换，数组顺序为:11，13，8，9，14。第二趟:11与13比较，13与8比较并交换，13与9比较并交换，13与14比较，数组顺序为:11，8，9，13，14.这种情况，选项里没有答案，故放弃。第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则:第一趟:9与8比较，8与13比较并交换，8与11比较并交换，8与14比较并交换，数组顺序为:8，14，11，13，9。第二趟:9与13比较并交换，9与11比较并交换，9与14比较并交换，9与8比较，数组顺序为:8，9，14，11，13。故选:C。 8.答案：A [解析]据题意:该数组进行从大到小排序，有两种情况:第1种情况:从数组第1个到最后一个元素向后走访数组，进行数据比较，则:第一趟:11与13交换，数组顺序为:14，13，11,8，9,第二趟:8与9交换，数组顺序为:14，13，11，9，8，排序完成;所以第1种情况共排序2遍，交换2次。第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则:第一趟:9与8交换，13与11交换，数组顺序为:14，13，11，9，8，排序完成，所以第2种情况共排序1遍，交换2次。故选:A。 9.答案：D [解析]数据序列“18，13，15，2，1，20”进行排序，第一轮排序后的结果为“1，18，13，15，2，20”，可知冒泡算法的思想进行升序排列数组，要完成最终的排序需要进行9轮比较最终完成故选:D。 10.答案：C [解析]本题的6个数据“7，3，8，2，1，9”，第一次:“3，7，2，1，8，9”，交换次数为3次，第二次:“3，2，1，7，8，9”，交换次数为2次，第三次，“2，1，3，7，8，9”交换次数为2次，第四次1，2，3，7，8，9，交换次数为1次，总次数为3+2+2+1=8次。故选:C。 11.答案：C [解析]由冒泡排序算法基本思想知:依次比较两个相邻的数据，如果顺序错误就交换它们，所以相邻的数据一定会比较，但不一定交换，所以B错误，C正确;冒泡排序中，几个数要进行n -1次比较，在第j趟中要进行n-j趟比较，所以A错误;在排序算法中，根据原始数据的不同，不同算法的效率不一样，速度也不一样，所以D错误。故选C。 课 堂 小 结 课堂小结 一、排序 1.概念 2.存储方式 数组、链表 二、常见的排序算法 1.拓展链接：Python中的排序函数 列表自带的sort方法、内建函数sorted方法 2.冒泡排序 （1）概念 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 三、排序算法的应用 作 业 设 计 1.用冒泡排序算法对12、34、45、56、66五个数进行升序排序，下列叙述正确的是（） A.每一趟都不需要进行数据比较 B.整个冒泡排序的过程都没有数据被交换 C.冒泡排序只能从小到大排序 D.5个数一趟比较4次，要进行4趟比较，所以共进行16次比较 2.采用冒泡排序算法对数据序列“8，3，5，2，0，9”进行排序，第一轮排序后的结果为“0，8，3，5，2，9”，则整个序列完成排序的交换次数是() A.6次 B.7次 C.8次 D.9次 3.对“842715”中的数字进行选择排序中的两遍“加工”即为某密码锁 的密码，则该密码可能是( ) A.842715 B.142785 C.872415 D.124578 4.对5个数字“2、8、6、1、7”进行两遍冒泡排序后即为某密码锁的密码，该密码可能是（） A.12687 B.12867 C.28617 D.12678 5.下面关于冒泡排序说法正确的是（） A、只能从小到大排序 B、可以一次比较三个以上的元素 C、当比较的两个数逆序时，交换顺序 D、只能比较数据 6.对下列一组原始数组:13，15，2，11，8，18进行选择排序，第一趟排序介绍，数组的状态不可能是（） A.2，15，13，11，8，18 B.18，15，2，11，8，13 C.13，15，2，11，18，8 D.13，15，18，11，8，2 7.某 Python程序如下： a=[3,1,9,7,6,3] n=len(a) for i in range(1,n): for j in range(n-2,i-2,- 1): if a[jka[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序运行后，数组a的值是（） A.[9,3,1,7,6,3] B.[9,7,6,3,3,1] C.[1,3,3,9,7,6] D.[1,3,3,6,7,9] 8.有如下python程序段: a =[33,24,45,16,77 for i in range (0, 2): for j in range (4,i,-1): if a|j]> a[i]: a|j],a[i]=a[i],alj] 经过该程序段“加工”后，数组元素a的值依次为() A.77，45，33，16，24 B.77，33，45，16，24 C.77，24，45，16，33 D.77，45，33，24，16 9.有如下python程序段: a = [0]*6 b =[76,88, 84, 91, 99, 80] for i in range (6): for j in range (i + 1, 6): if b[j] > b[: a[i]+=1 else: a[j]+=1 print(a) 该程序段运行后，列表a的值为() A.[5,2,3, 1,0,4 B.[0, 3, 2, 4,5, 1] C.[10,6, 4,8, 12,2] D.[6,3, 4,2,1,5] 10.有如下程序段 a=[8，1，2，6，3，4，7，5] n=len (a) for i in range (0，n，2) for j in range(n-1,i*2+1,-1): if aj]<a[j-2]: a[j]，a[j-2]=a[j-2]，a[j] 则程序运行后，a[4]的值为() A.3 B.4 C.7 D.8 11.运行以下程序段后,输出的列表为（） def bubble_sort(L): length=len(L) for i in range(l ,3): for j in range(0,length-i): if L[j]<L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp A=[6,8,2,4,3,7] bubble_sort(a) print(a) A.[2.3.4.6.7,8] B.[8,7.6.4.3,2] C. [8,6.4.7.3.2] D. 16,8.7,4.3,2] 12.实现某排序算法的部分Python程序段如下 def bubble_sort(L): length=len(L) for i in range(1,5): for j in range(0,length-i): if L[j]<L[j+1]: temp=L[j] L[j]=L[j+1] L[j+1]=temp ans.append(L[length-i]) a=[3,9,2,1,5,2,6] ans=[ ] bubble_sort(a) print(ans) 经过该程序段“加工”后,输出的结果是() A.[9,6,5,3] B. [1,2,2,3] C.[3,9,2,1] D.[6,2,5,1] 13.有如下Python 程序段: A=[15,20,11,6,12,8,7,3] for i in range(1,3): for j in range(0,8-i): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] 程序段运行后,数组a中的数据依次为 A.3,6,7.8.11.12.15,20 B15,11.6,12,8,7.3,20 C.11,6,12,8.7,3,15,20 D.6,11,8.7.3.12.15.20 14.有如下 python 程序段： n=6 a = [] for i in range(3): for j in range(n - i - 1): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] print(a) 数组元素a（1）到a（6）的数据依次为“50，31，18，42，37，23”，则此程序运行完成后数组元素的数据依次是（　　） A. 50，42，37，31，23，18 B. 18，23，31，50，37，42 C. 18，31，23，37，42，50 D. 18，23，31，37，42，50 15.有如下Python程序段 a= 51,73,74,85,94,88 cnt=0 for i in range (len(a)-1,0,-1): flag = False for j in range (i): if a[j] > alj+ 1]: alj], a[j+ 1]= a[j+ 1],a[j] flag = True cnt+=1 if not flag: break 则程序运行后，cnt的值为() A.0 B.1 C.2 D.3 16.有如下Python程序段: a=[40，14，10，19，24，45];n=len(a) for i in range(n-1): Flag=False for j in range (n-1,i,-1): if a[j]>a[j-1]: a[j], a[j-1]=a[j-1], a[j] Flag=True if not flag: break 执行该程序段后，下列说法正确的是() A.该程序实现将数组a升序排序 B.元素14在程序运行过程中被交换2次 C.该程序的时间复杂度为〇(n) D.程序结束后，i的值为3 17.某Python程序如下 for i in range(2,12): if 12%i == 0: Mn=i break 程序运行后,变量mn的值是() A.1 B.2 C.6 D.12 参考答案： 1.答案：B [解析]题中五个数已经是升序数列了，所以在进行冒泡排序时虽然还进行比较，但是不会进行数据的交换.5个数只有第一趟比较4此，找到了最小值后比较就会少一次.故选:B. 2.答案：D [解析]本题的6个数据，835209第一次:083529，交换次数为4次(“8，3，5，0，2，9”，“8，3，0，5，2，9”，，0，3，5，2，9”，“0，8，3，5，2，9第二次:028359，交换次数为3次(“0，3，2，5，9”，“0，8，2，3，5，9”，2，8，3，5，9”)，第三次，023859，交换次数为1次(“0，23，8，5，9”)第四次，023589，交换次数为1次(“0，23，5，8，9”)，总次数为4+3+1+1=9次。故选:D。 3.答案：.C [解析]如果选择升序排序,第1遍后为142785.找到最小的值与第1个位置交换,其他不动。第2遍后为124785。如果选择是降序排序,第1遍后为842715.因为第1个位置数本身是最大,不用交换。第2遍后为872415。第二大的数与第2位置数交换。 4.答案：A [解析]据题意:从4个答案可以看出这密码是从小到大排列的，有两种情况:第1种情况:从数组第1个到最后一个元素向后走访数组，进行数据比较，则: 第一趟:2与8比较，8与6比较并交换，8与1比较并交换，8与7比较并交换，数组顺序为:2、6、1、7、8； 第二趟:2与6比较，6与1比较并交换，6与7比较，7与8比较，数组顺序为:2、1、6、7、8，选项中没有次序列，故此种情况放弃。 第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则: 第一趟:7与1比较，1与6比较并交换，1与8比较并交换，1与2比较并交换，数组顺序为:1、2、8、6、7； 第二趟:7与6比较，6与8比较并交换，6与2比较，2与1比较，数组顺序为:1、2、6、8、7，这是选项A的数组。 故选:A。 5.答案：C [解析]冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，对相邻两个数进行比较，将较小的数据换到上面的一个元素中（或将较大的数据换到下面的一个元素中）。 6.答案：C [解析]如果该数组升序排列，会有两种排序情况:①第一趟排序要在所有数里选择最小数2，把它与第一个数13交换位置，放在数组最前面，得到数组为:2，15，13，11，8，18，故A选项正确; ②第一趟排序要在所有数里选择最大数18，即数组最后一个数，所以不发生数字交换，故第一趟排序结束后，数组还是原来的顺序，如果该数组降序排列，也会有两种排序情况: ①第一趟排序要在所有数里选择最小数2，把它与最后一个数18交换位置，放在数组最后 面，得到数组:13，15，18，11，8，2，故D正确; ②第一趟排序要在所有数里选择最大数18，把它与数组第一个数13交换位置，放在数组最前面，得到数组:18，15，2，11，8，13，故B正确; 综上:第一趟排序后，选项A、B、D，或者数组原来顺序 4种情况会出现，只有C的数组不会出现;故选C。 7.答案：B [解析]程序功能是使用冒泡排序算法对数组a进行降序排序。注意比较的两个相邻元素是a[j}和a[j+1],故变量j的取取值范围为 range(n-2,i-2,-1)。 8.答案：A [解析].foriinrange(0,2):外循环次数=2，内循环forjinrange(4,i,-1):，内循环i.fa [j] > al]:a|j]与a[]交换，i=0，第一次比较完成后a =[77,24,45,16,33]，i=1第二次比较完成后，a=[77,45,33,16,24，A选项正确。故选:A。 9.答案：A [解析]阅读程序段可知，程序实现的是列表中元素的降序排列，各元素下标的交换次数，已知列表[76,88,84,91,99,80]中76为最小的元素，所以需要比较5次，故a中对应的元素为5，同理分析后面的元素得到[5,2,3,1,0,4]。故选:A。 10.答案：B [解析]阅读程序可知，外循环i的取值分别为0，2，4，6。当i=2时，内循环j的取值范围最大为[7，2]，此时的排序适用于整个数组，根据 a[j]<a[j-2]的条件进行交換a[j]，a[j-2]=a[j-2]，a[j]的值后，最终得到a[4]的值为4，因为第一个元素的下标为0。故选:B。 11.答案：C [解析]观察代码“foriin range(1,3)”,变量i只执行两次,循环体是利用冒泡排序,从前往后比较实现降序。i=1执行完后a的状态为[8,6,4,3,7,2],i=2执行完后a的状态为[8,6,4,7.3,2],所以答案选C。 12.答案：B [解析]该程序中,兩数bubble_sort(L)是利用冒泡排序的思想对数组L按从前往后比较方式进行降序排序,一趟加工完成后最后面的元素是当前的最小数据,将该元素添加进数组ans,所以第一趟完成后数组ans中的元素是[1],观察到i的循环范围是1~4,即只进行4趟比较与交换,数组ans中依次记录[1,2,2,3],因此正确答案是B。 13.答案：C [解析]本题主要考查的是冒泡排序。本题的功能是将数组a中的数据进行升序排序,求排序两遍后的数据序列情况，第一遍排序后的结果为“15,11,6.12.8,7,3,20”,第二遍排序后的結果为“11,6,12.8.7,3,15,20”,因此等案为C。 14.答案：C [解析]第一步：if a（j）＞a（j+1）→从小到大排序，现在确定最大→排除A；第二步：50，31，18，42，37，23（i = 1）→31，18，42，37，23，50（i = 2）→18，31，37，23，42, 50（i = 3）→18，31，23，37，42, 50。故选C。 15.答案：B [解析]本题考查的python程序的调试与运行。Por语句是循环语句，它的格式是:For变量=初值To终值|Step步长]循环体Nert变量。Range (start, stop[,step])start:计数从start开始。默认是从0开始。例如range(5)等价于range(0,5);stop:计数到stop结束，但不包括stop。阅读程序可知，本程序段实现的是数据的升序排列，需要交换的元素只有94，88，所以共执行一次交换，得到cnt的值为1。故选:B。 16.答案：D [解析]本题主要考查排序算法及Python程序实现。该程序实现将数组a降序排序;元素14在程序运行过程中被交换3次;该程序的时间复杂度为0(n2);当i-3时，a已有序，因此程序结束后，i的值为3，故本题选D选项。 17.答案：B [解析]循环变量i的范围为2~11,若12能被i整除,则将i的值赋给变量mn，并使用break退出循环,所以变量mn存储的是12除1以外的最小因数,结果为2. 反 思 评 价 本堂课讲解的是排序算法方面的知识，比较难懂，只有通过大量的举例来充实课堂。通过列举实例，分析排序算法和冒泡算法的概念和特性，让学生们通过实际问题，恰当地选择排序算法的方法，并总结排序算法的概念、特性及基本操作。体验用排序算法解决问题的基本流程，逐步形成运用排序算法解决问题的思维方式和学科方法。最终能够熟练掌握排序算法的基本操作。 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$