资源简介 (共84张PPT)课时3 数据排序第五章 数据结构与算法1.通过具体实例,理解排序的概念和基本方法。2.能根据实际的应用场景,选择合理的数据结构,并使用排序算法来编程解决问题。目 录CONTENTS知识梳理01例题精析02随堂检测03巩固与提升04知识梳理11.排序(1)排序的概念排序是指将一些______的数据变成______的数据。(2)排序方式排序方式主要有:______(从小到大排列)和______(从大到小排列)。(3)待排数据的存储方式待排数据通常存储在数组或链表中。无序有序升序降序2.常见的排序算法常见的排序方法有:____________、____________、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。冒泡排序选择排序3.利用Python的sort方法和内建函数sorted排序(1)sort方法说明:使用sort方法对列表中的数据进行排序时,将______对列表进行排序,不会产生______列表。例:列表lista=[36,23,12,17,22,19,28],可用命令lista.sort()将列表lista中的数据进行升序排序,可用命令lista.sort(reverse=True) 将列表lista中的数据进行降序排序。直接新的(2)sorted函数说明:使用sorted函数进行排序时,将排好序的数据返回一个____________。例:lista=[36,23,12,17,22,19,28],执行语句listb=sorted(lista)后,列表listb中的元素为[12,17,19,22,23,28,36,],从而实现升序排序;执行语句listc=sorted(lista,resverse=True)后,列表listc中的元素为[36,28,23,22,19,17,12],从而实现降序排序。新的序列4.冒泡排序(1)冒泡排序的基本思想冒泡排序是在数列中对______两个数据依次进行______和位置调整,让较大的数“下沉(或上冒)”,较小的数据“上冒(或下沉)”的一种排序技术。(2)冒泡排序的特点①______两个数据进行比较。②n个数据完成排序,共进行_________趟(遍)排序。④n个数据完成排序,其时间复杂度为___________。相邻比较相邻n-1O(n2)5.冒泡排序算法的程序实现说明:对列表list1中的数据进行升序排序def bubble_sort(list1):count=len(list1)#count个数排序共需进行count-1趟for i in range(1,count):#每一趟排序从前往后进行,比较相邻两个数for j in range(_______________): if _____________________: list1[j],list1[j+1]=list1[j+1],list1[j]return list10,count-ilist1[j]>list1[j+1](1)冒泡排序进行时,数据的比较可以由前往后进行,即list1[j]与listl[j+1]比较;也可以由后往前进行,即list1[j]与list1[j-1]比较,此时应将循环条件“for j in range(0,count-i):”修改为“for j in range(count-1,i-1,-1):”。(2)若要将数据按降序排列,只需将语句“if list1[j]>list1[j+1]:”修改为“if list1[j]例题精析2例1 采用冒泡排序算法对数据序列“21,15,23,26,33,18,46,17”完成升序排序,理论上讲共需进行排序的遍数为( )A.3遍 B.4遍 C.7遍 D.8遍C解析 共有8个数据,共需要进行7遍排序, 因此答案为C。变式训练 采用冒泡排序算法对数据序列“16,11,8,9,21,32,28”完成升序排序,共进行数据交换的次数为( )A.3次 B.4次 C.5次 D.6次解析 本题主要考查的是冒泡排序思想。排序过程如下:D原始数据 16,11,8,9,21,32,28 交换次数第1遍完成后的数据为 8,16,11,9,21,28,32 交换3次第2遍完成后的数据为 8,9,16,11,21,28,32 交换2次第3遍完成后的数据为 8,9,11,16,21,28,32 交换1次第4遍完成后的数据为 8,9,11,16,21,28,32 不交换… … 不交换因此,完成升序排序,共交换的次数为6次,答案为D。例2 采用冒泡排序算法对8个数据“48,65,29,16,22,75,36,41”进行降序排序,则第3遍的排序结果是( )A原始数据 48,65,29,16,22,75,36,41第1遍完成后的数据为 75,48,65,29,16,22,41,36第2遍完成后的数据为 75,65,48,41,29,16,22,36第3遍完成后的数据为 A.75,65,48,41,36,29,16,22B.75,65,48,41,29,16,22,36C.75,65,48,41,36,29,22,16D.75,65,48,41,29,22,16,36解析 本题主要考查的是冒泡排序的实现。根据第1、2遍可知,冒泡排序是从后往前进行降序排序,根据第2遍的结果可推出第3遍的排序结果为75,65,48,41,36,29,16,22,因此,答案为A。变式训练 小明对6个数字“3,5,8,2,6,1”进行两遍冒泡排序后的数字序列设置为办公室门的密码锁,则该密码可能是( )①1 2 3 5 8 6 ②8 6 3 5 2 1 ③1 2 3 5 6 8④3 2 5 1 6 8 ⑤8 5 6 3 2 1A.①②③④⑤ B.①②C.④⑤ D.①②④⑤解析 本题主要考查的是冒泡排序思想。排序方式有升序和降序,排序的方向可以从前往后或从后往前,因此要分4种情况进行讨论分析。如果是升序排序,从前往后进行两遍后数据序列为②,从后往前进行两遍后数据序列为①;如果是降序排序,从前往后进行两遍后数据序列为⑤,从后往前进行两遍后数据序列为④。因此,①②④⑤都有可能,答案为D。D例3 列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:n=8for i in range(1,n-1): for j in range(1,n-i-1): if s[j]>s[j-1]: s[j],s[j-1]=s[j-1],s[j]该程序段实现的是( )A.s[0]到s[5]的降序排列 B.s[1]到s[6]的降序排列C.s[1]到s[7]的升序排列 D.s[2]到s[6]的升序排列解析 本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1,5],条件s[j]>s[j-1]表示当后一个数大于前一个数时要发生交换,实现降序排列。参加排序元素仅s[0]~s[5]。A变式训练 有如下Python程序段:Cb=[17,8,6,15,21,36,18,33]n=len(b)for i in range(1,4):for j in range(n-1,i-1,-1):if b[j]>b[j-1]: b[j],b[j-1]=b[j-1],b[j]经过该程序段“加工”后,列表b中的元素为( )A.[36,33,17,8,6,15,21,18]B.[36,33,21,17,15,8,6,18]C.[36,33,21,17,8,6,15,18]D.[36,33,21,18,17,8,6,15]解析 本题主要考查的冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法进行降序排序3遍,数据比较是从后往前进行的,进行第1遍排序后的数据序列为[36,17,8,6,15,21,33,18],进行第2遍排序后的数据序列为[36,33,17,8,6,15,21,18],进行第3遍排序后的数据序列为[36,33,21,17,8,6,15,18],因此答案为C。例4 小明编写程序实现数据排序功能,部分程序如下:n=len(d)for i in range(1,n): for j in range(n-i-1,-1,-1): if d[j]>d[j+1]: d[j],d[j+1]=d[j+1],d[j]print(d)A.d=[9,6,5,8] B.d=[9,8,6,5]C.d=[8,9,5,6] D.d=[6,5,9,8]解析 实现从后往前冒泡升序排列,前面的数据先有序,但右端没有固定,每趟都在缩减,因此有些数是排不到的。AB选项排序后均为5,6,9,8,无序,可以检测。C选项排序后为5,8,9,6,无序,可以检测。D选项排序为升序,与正确算法结果相同,无法检测。D变式训练 有如下Python程序段:d=[12,8,6,3,8,10]i=0;q=0;flag=Falsewhile i flag=True for j in range(len(d)-1,q,-1):程序运行后,加框处语句执行次数为( )A.15 B.12 C.9 D.8解析 程序实现从后往前降序排序,q记录有序数据的个数,第1趟比较了5次,第2趟比较了3次,d的值为[12,10,8,8,6,3],q的值为4,排序后,数据有序,第3趟只比较1次,数据无交换,结束排序,比较次数分别为5+3+1=9。C随堂检测31.采用冒泡排序算法对数据序列“9,7,6,8,5,4,2,3”进行升序排序,约定从前往后进行数据比较及位置交换,则第2趟排序结束时的数据序列为( )A.7,6,8,5,4,2,3,9 B.6,7,5,4,2,3,8,9C.6,5,4,2,3,7,8,9 D.6,7,4,2,3,5,8,9B解析 第1趟排序结束时的数据序列为7,6,8,5,4,2,3,9,第2趟排序结束时的数据序列为6,7,5,4,2,3,8,9。 因此,答案为B。2.采用冒泡排序算法对数据序列“6,8,9,5,4,2,7,3”进行降序排序,约定从后往前进行数据比较及位置交换,则进行第2趟排序时的数据交换次数为( )A.0次 B.1次 C.2次 D.3次C解析 第1趟排序结束时的数据序列为9,6,8,7,5,4,2,3,数据交换5次,第2趟排序结束时的数据序列为9,8,6,7,5,4,3,2,数据交换2次,因此答案为C。3.有如下Python程序段:Cb=[99,88,77,66,55,61,71,81]count=len(b)for i in range(1,4):for j in range(0,count-i): if b[j]>b[j+1]: b[j],b[j+1]=b[j+1],b[j]经过该程序段“加工”后,列表b中的元素为( )A.[77,66,55,61,71,81,88,99] B.[55,61,66,71,77,81,88,99]C.[66,55,61,71,77,81,88,99] D.[66,61,55,71,77,81,88,99]解析 本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法进行升序排序3遍,数据比较是从前往后进行的,第1遍排序后列表b中的元素为[88,77,66,55,61,71,81,99],第2遍排序后的数据序列为[77,66,55,61,71,81,88,99],第3遍排序后的数据序列为[66,55,61,71,77,81,88,99],因此答案为C。4.有如下Python程序段:A解析 加框处语句表示交换次数,从条件s[j]s=[2,3,8,7,5]for i in range(len(s)-1): for j in range(len(s)-1,i,-1): if s[j]执行该程序段,加框处语句被执行的次数是( )A.3 B.6 C.8 D.105.有如下Python程序段:from random import randinta=[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+1]=a[j] j-=1 a[j+1]=keyBA.[3,6,8,10,12] B.[1,5,8,9,12]C.[6,10,10,12,12] D.[8,9,10,10,12]解析 本题考查排序算法和随机数函数。首先列表a中的初始值是[1,10]内的5个随机数。key的取值只能是6、8、10、12。while循环会将key插入列表a的合适位置上,使得列表a的值非降序排列,因此选项A、C、D都是有可能的。6.有如下Python程序段:s=″ccbbac″a=[i for i in range(6)]for i in range(5): for j in range(5-i): if s[a[j]]>s[a[j+1]]: a[j],a[j+1]=a[j+1],a[j]print(a)C运行该程序段输出的结果为( )A.[4,3,2,5,1,0] B.[4,5,3,2,1,0]C.[4,2,3,0,1,5] D.[4,3,2,5,0,1]解析 本题考查索引排序。数组a存储的0-5的索引位置,程序实现从前往后冒泡,当条件s[a[j]]>s[a[j+1]]成立时交换,实现升序排列,因此排序后的结果是abbccc,找到这些字母的索引位置。7.有如下Python程序:A解析 从后往前冒泡,排了3趟。a=[1,5,2,9,6,7]n=len(a)for i in range(n∥2): for j in range(n-1,i,-1):if a[j]>a[j-1]: a[j],a[j-1]=a[j-1],a[j]执行该程序段后,a的值是( )A.[9,7,6,1,5,2] B.[9,7,6,5,2,1]C.[1,2,5,6,7,9] D.[9,6,7,5,2,1]8.有如下Python程序段:L=[21,12,13,17,16,15,20,28,11]def shengxu(a,b):for i in range(0,b-a):for j in range(__________): if L[j]>L[j+1]: L[j],L[j+1]=L[j+1],L[j]shengxu(3,7)print(L)C若要实现列表L中L[a]到L[b]之间的数升序排列(不改变其余元素的位置),划线处的代码应为( )A.i,b B.0,b-iC.a,b-i D.b-1,a-i-1,-1解析 外循环控制排序的次数,也与排序的区间位置有关。冒泡排序必须是一端固定,另一端随着排序的过程将不断地缩短。若从前往后冒泡,则排序的初值必须为a,第一趟排序的区间是最长的,此时i的值为0,最后位置为b,而j+1到过b时,j的值为b-1,若要取到b-1,则终值必须为b,结合i的值,终值为b-i。9.有如下Python程序段:a=[3,8,6,2,1,0,7]n=len(a)for i in range((n-1)∥2): j=0;k=1 while j if a[j]*k>a[j+2]*k: a[j],a[j+2]=a[j+2],a[j] j=j+1;k=-kA执行该程序段,则a[4:7]的值为( )A.6,0,7 B.6,7,8 C.3,8,1 D.6,8,7解析 当k为1时,a[j]>a[j+2]表示升序排序,k为-1时,降序排序;程序实现奇位升序,偶位降序排列。4巩固与提升基础巩固能力提升A.使用冒泡排序算法完成n个数据的排序,共需要进行n-1趟B.冒泡排序是通过比较相邻两个元素的大小和位置交换来完成的C.冒泡排序进行时,相邻元素的比较和交换只能从前往后进行D.使用冒泡排序算法完成6个数据的排序,最坏情况下,数据交换次数为15次C解析 冒泡排序进行时,相邻元素的比较和交换可以从前往后进行,也可以从后往前进行,因此答案为C。2.采用冒泡排序算法完成数据序列“9,8,7,6,5,2,3,4”的升序排序,则数据交换的次数为( )A.18次 B.22次 C.25次 D.27次C解析 例如排序方向从前往后进行,排序过程如下:原始数据 9,8,7,6,5,2,3,4 交换次数第1遍完成后的数据为 8,7,6,5,2,3,4,9 交换7次第2遍完成后的数据为 7,6,5,2,3,4,8,9 交换6次第3遍完成后的数据为 6,5,2,3,4,7,8,9 交换5次第4遍完成后的数据为 5,2,3,4,6,7,8,9 交换4次第5遍完成后的数据为 2,3,4,5,6,7,8,9 交换3次第6遍完成后的数据为 2,3,4,5,6,7,8,9 不交换第7遍完成后的数据为 2,3,4,5,6,7,8,9 不交换排序完成时,共进行7+6+5+4+3=25次,因此,答案为C。3.有8个学生的体重(单位:公斤)依次为“50.5,60.8,65.6,80.8,48.5,52.1,61.3,70.2”,若采用冒泡排序算法对其进行升序排序,则第3遍的排序结果是( )D原始数据 50.5,60.8,65.6,80.8,48.5,52.1,61.3,70.2第1遍完成后的数据为 48.5,50.5,60.8,65.6,80.8,52.1,61.3,70.2第2遍完成后的数据为 48.5,50.5,52.1,60.8,65.6,80.8,61.3,70.2第3遍完成后的数据为 A.48.5,50.5,52.1,60.8,65.6,61.3,80.8,70.2B.48.5,50.5,52.1,60.8,61.3,65.6,70.2,80.8C.48.5,50.5,52.1,60.8,65.6,70.2,80.8,61.3D.48.5,50.5,52.1,60.8,61.3,65.6,80.8,70.2解析 观察第1遍和第2遍排序可知,排序是从后往前进行的,排序方式为升序,因此容易得出第3遍的排序结果为48.5,50.5,52.1,60.8,61.3,65.6,80.8,70.2,答案为D。4.对列表b中的n个元素进行降序排序,其排序算法的Python部分程序段如下: b=[34,435,23,98,788,30,77] n=len(b) count=0 for i in range(0,n-1):for j in range(①__________): if ②________________: count=count+1 b[j],b[j+1]=b[j+1],b[j] print(″排序后的序列为:″,b) print(″数据交换次数为:″,count)A程序划线①②处应填入的语句为( )A.①0,n-i-1 ②b[j]B.①n-1,i,-1 ②b[j]>b[j-1]C.①0,n-i ②b[j]D.①0,n-i-1 ②b[j]>b[j+1]解析 根据交换语句b[j],b[j+1]=b[j+1],b[j]可知,排序方向为从前往后进行的,因此①处应为0,n-i-1, ②处代码为b[j]5.有如下 Python 程序段:a=[19,17,6,9,8]n=len(a)f=True;i=4;k=0while i>0 and f: f=False for j in range(i): if a[j] a[j],a[j+1]=a[j+1],a[j] k=k+1;f=True i=i-1D该程序段执行后,下列说法正确的是( )A.数组a各元素的值是:6 8 9 17 19B.变量 k 的值为 3C.数组元素 6 在此过程中共交换了 3 次D.变量 i 的值为 2解析 本题考查冒泡排序算法。相邻两个数据a[j]6.有如下Python程序段: b=[5,32,17,22,15,36,41,55] count=len(b) for i in range(1,3):for j in range(1,count-i): if b[j] b[j],b[j+1]=b[j+1],b[j]C经过该程序段“加工”后,列表b中的元素为( )A.[32,22,17,36,41,55,15,5]B.[32,22,36,41,55,17,15,5]C.[5,32,22,36,41,55,17,15]D.[5,32,36,41,55,22,17,15]解析 本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法对后7个数据进行2趟降序排序,数据比较是从前往后进行的,需注意的是列表b中的第1个元素(索引位置0)不参与排序,第1遍排序后列表b中的元素为[5,32,22,17,36,41,55,15],第2遍排序后的数据序列为[5,32,22,36,41,55,17,15]。因此,答案为C。7.如下 Python 程序段:s=list(″bcaabca″)n=len(s)for i in range(1,n): for j in range(n-1,i-1,-1):if s[j]=='a' and s[j-1]!='a': s[j],s[j-1]=s[j-1],s[j]print(s)C执行该程序段后,输出的内容为( )A.['b','c','b','c','a','a','a'] B.['b','b','c','c','a','a','a']C.['a','a','a','b','c','b','c'] D.['a','a','a','b','b','c','c']解析 本题考查冒泡排序的变形。根据 if 条件s[j]=='a' and s[j-1]!='a'可以看出,取字符串 s 中字符时,若当前字符 s[j]为'a'但 s[j-1]不为'a',交换s[j-1]与s[j]的位置。因此,该程序段的功能为将字符'a'前移,其他字符保持原位置不变,交换后的结果为C.['a','a','a','b','c','b','c']。A.这轮排序,有可能没发生数据交换B.这轮排序,有可能只发生了1次数据交换C.排序结束后,数据是升序的D.完成全部排序后,数据交换的次数和冒泡的方向无关A解析 本题考查冒泡排序。经过一轮后最小数在最前面,可知,该冒泡排序是从后往前冒泡,升序。A选项原始数据最小数2不在最前面,一定会发生交换。若原始数据就是一趟排序结果,9在中间,无论是从后往前,还是从前往后,都要发生数据交换。B选项若原始数据如果为“2,3,5,9,6,7”,那么就发生了一次交换。C选项从一趟结果来看,是升序排列。D选项数据的交换取决于逆序对的个数,与排序方向无关。9.有如下 Python 程序段:a=[3,6,7,2,8,2]; b=[5,3,7,7,7,4]for i in range(len(a)-1): for j in range(0,len(a)-i-1):if a[j]>a[j+1] or a[j]==a[j+1] and b[j] a[j],a[j+1]=a[j+1],a[j] b[j],b[j+1]=b[j+1],b[j]C执行上述程序段后,a[1]与 b[1]的值分别是( )A.8,7 B.7,7 C.2,4 D.2,7解析 本题考查双关键字排序。主关键字为a数组,次关键字为b数组,当a[j]>a[j+1]就交换数据,表示升序。当a[j]==a[j+1] and b[j]10.使用列表a 和列表b 分别存储学生的总分和考号,已知考号为b[i]的学生的总分为a[i],使用 Python 编程实现如下功能:将成绩数据“按总分降序排序、总分相同按学号升序排序”,代码如下。n=len(a)for i in range(1,n): for j in range(0,n-i): a[j],a[j+1]=a[j+1],a[j] b[j],b[j+1]=b[j+1],b[j]C上述程序段中方框处可选代码为: ①a[j]>a[j+1]②a[j]==a[j+1] ③a[j]b[j+1]则(1)(2)(3)处代码依次为( )A.③②④ B.①⑤⑥ C.③②⑥ D.①⑤④解析 本题考查冒泡排序。从 for j in range(0,n-i)可知,从前向后冒泡,相邻两数两两比较;比较规则如下:第 j 个比 j+1 个成绩小则交换,选语句 ③。第 j 个和第 j+1 个成绩相同,选语句②,且第 j 个考号比第 j+1 个大,选语句⑥。11.某 Python 程序如下:s=[2,3,4,9,7,8,5]n=len(s)for i in range(n-1): for j in range(n-1,i,-1):if s[j] s[j],s[j-1]=s[j-1],s[j]D下列说法正确的是( )A.整个加工过程总的交换次数为 21B.该程序段执行后,s 的值为[9,8,7,5,4,3,2]C.若s的初始值已有序,则该算法的时间复杂度为 O(1)D.每一遍加工中,最小的元素“上浮”解析 本题考查排序算法。当条件s[j]12.火车调度台是实现火车车厢整理的平台,当相邻2节车厢序号不符合整理要求时,可以对调2节车厢,实现序号顺序调整。相邻2个进行符合目标的交换,和我们学习的冒泡排序思想一致,所以这个调度过程可以用冒泡排序实现。为了提高效率,对冒泡排序做了优化,请完善下列代码:nums=[3,1,2,4,5,6]①____________k=n-1for i in range(n-1):②______________for j in range(k):if (nums[j]>nums[j+1]): nums[j],nums[j+1]=nums[j+1],nums[j] ③____________ ex_flag=Trueif ex_flag:breakprint(nums)答案 ①n=len(nums) ②ex_flag=False ③k=j解析 本题主要考查冒泡排序算法的优化。题目中实现优化的方法是,当某趟排序过程中没有发生数据的交换时,说明数据已经有序,结束数据的排序;同时,通过记录最后发生数据交换的位置,缩小数据排序的范围。空①处n=len(nums),获得数据的规模,空②处ex_flag=False,当发生数据交换时,ex_flag会被赋值为True,空③处k=j表示记录最后发生数据交换的位置。13.小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将列表b中奇数位置的元素、偶数位置的元素分别进行排序,然后再进行后续处理。算法的Python程序段如下,请回答下列问题。 b=[26,12,30,23,32,28,49,35,38] n=len(b) for i in range(1,(n-1)∥2):for j in range(0,n-i*2): if ①________________: b[j],b[j+2]=b[j+2],b[j] for i in range(1,n∥2+1): j=2*i-1 if b[j] b[j],b[j-1]=b[j-1],b[j] t=b[i] j=i-1 while t b[j+1]=b[j] j-=1 ②____________________ print(″处理后的数据序列为:″,b)(1)加框处的代码有误,请改正。(2)请在程序划线处填入合适的代码。答案 (1)2,n,2 (2)①b[j]>b[j+2] ②b[j+1]=t解析 本题主要考查排序的综合应用。本题在排序过程中,使用到了冒泡排序和插入排序算法,本题的算法思想是:首先利用改进的冒泡排序分别对数列b中奇数位置和偶数位置上的元素进行升序排序,排序结束后的数据序列特点为:奇数位置上的元素已升序排列,偶数位置上的元素已升序排列;然后从第2个元素(索引位置1)开始,让偶数位置上的元素和它前面奇数位置上的元素比较,通过数据交换使得它们变为升序,此时奇偶数据对也已升序排列;最后从第3个元素位置,将奇数位置上的元素插入到前面有序的数列中,从而实现整个数列的升序排序。因此,加框处的代码修改为2,n,2,划线①处应填入的语句为b[j]>b[j+2]。在插入排序中需注意的是当前元素应插入的位置为j+1,因此,划线②处应填入的语句为b[j+1]=t。14.小明为了研究冒泡排序过程中数据的“移动”情况,编写了一个Python程序,功能如下:第一行显示排序前的数据,输入初始位置(即下标值)后,输出指定初始位置的数据在排序过程中的位置变化情况,最后一行输出排序后的数据。程序运行示例如图所示。请输入初始位置(索引值):2排序前数据序列为:[43,23,65,12,26,33,58,19]位置变化情况:2→1→0排序后的数据序列为:[65,58,43,33,26,23,19,12]实现上述功能的Python程序如下,请回答下列问题。 a=[43,23,65,12,26,33,58,19] n=len(a) pos=int(input(″请输入初始位置(索引值):″)) ①________________ print(″排序前数据序列为:″,a) for i in range(1,n):for j in range(0,n-i):if ②________________: a[j],a[j+1]=a[j+1],a[j]if pos==j: pos=j+1s=s+″→″+str(pos)elif ③________________: pos=j s=s+″→″+str(pos)print(″位置变化情况:″+s)print(″排序后的数据序列为:″,a)(1)请在程序划线处填入合适的代码。(2)程序运行样例如图所示,若输入的初始位置(索引值)为4,则输出的位置变化情况为__________________。解析 本题主要考查的是冒泡排序算法的综合应用。(1)字符串s记录的是初始位置元素的位置变化情况,显然,其初值为pos,需注意的是应先将pos转换为字符串后再赋值于s,因此①处代码为s=str(pos);数据的比较和交换是从左往右进行的,根据运行示例可知,是进行降序排序,因此②处语句为a[j]答案 (1)①s=str(pos) ②a[j](2)若输入的初始位置(索引值)为4,即研究列表中第5个数据(26)的位置变化,在排序过程中,26的位置变化情况为4→3→2→3→4。15.要向可容纳88966名观众的卢赛尔球场派送外卖是一项艰巨的任务,为了方便外卖派送,将球场观众席划分为A、B、C、D、E、F、G、H共8 个区,派单平台可以根据各区域订单数量安排派送人员,以提高外卖派送效率(一个派送人员只安排一个区域),平台根据订单总量与空闲派送人员数量计算人均派单量,按平均派单数计算各区域所需派送人员,但按此方法分配派送人员,人员总数可能超过空闲派送人员数,则删除超额派送人数,删除规则如下:每个有订单的区域至少保留一个派送人员,每个区域最多减去一个派送人员,优先删除派单尾数最少的区域中的派送人员,如果派单尾数相同,则在分配到派送人员数最多的区域中去掉一个派单人员,例如:A~H区域的订单数量分别为[468,329,392,247,38,180,263,82],此时空闲派单人员数为30人,人均派单数为67,则各区域分配的派单人员数量分别为7、5、6、4、1、3、4、2,合计32个派送人员,需减掉2超额派送人员,即从D区和H区派送人员中各减去1个。如下表所示:球场区域 A B C D E F G H 合计订单数量 468 329 392 247 38 180 263 82 1999所需派送人员 7 5 6 4 1 3 4 2 32派单尾数 66 61 57 46 38 46 62 15 391去除派单人员 -1 -1 -2实际派送人员数 7 5 6 3 1 3 4 1 30(1)数据如上表所示,如果F区退掉2份订单,重新计算并分配派送人员(整体调整),F区派送人员的人均派单量是________。(2)实现上述功能的Python程序如下,请在画线处填写正确的代码。#从数据库中读取各订单所在区域,如a=['A','B','H','F',……]qyn=8 #区域数量psryn=30 #配送人员数量rs=round(len(a)/psryn)b=[]for i in range(qyn): c=chr(i+65) #A的ASCII码是65 b.append([c,0,0]) #生成二维列表b=[['A',0,0],['B',0,0]……]for i in a: #统计各区域订单数量 ①________s=0for i in range(qyn) : ②________ if b[i][1]%rs!=0: b[i][2]+=1 s+=b[i][2]k=s-psryni=0while k>0: for j in range(qyn-1,i,-1): if ③______: b[j-1],b[j]=b[j],b[j-1] if b[i][2]>1: b[i][2]-=1 k-=1 i+=1(3)若函数中语句“s+=b[i][2]”缩进到了“if b[i][1]%rs!=0:”模块内,题中所给的样例数据运行结果__________(是/否)受到影响,将样例“E”区订单数量38修改为__________能测出程序存在的问题。答案 (1)89 (2)①b[ord(i)-65][1]+=1②b[i][2]=b[i][1]∥rs③b[j-1][1]%rs>b[j][1]%rs or b[j-1][1]%rs==b[j][1]%rs and b[j-1][2](3)否 67或67的倍数解析 本题考查二维数组应用和冒泡排序算法。(1)优先删除派单尾数最少区域中的派送人员,F区退掉2份订单,尾单数量为44,实际派送人员为2人,人均派单量为178/2=89。(2)①统计各区域订单数量,从条件b[i][1]%rs!=0来看,b[i][1]存储的是各区域的订单数量,数据库中读取各订单所在区域,需先将a数组中A-H转换成0-7的索引号,再对b数组进行累加计数。②计算所需派送人员。从语句k=s-psryn来看,s是所需派送人员人数之和,每个区域产生尾单后,所需派送人员增加1人,因此先计算整数倍的值。③找到去除派单人员的条件。k是需去除派单人员,按尾单人数采用冒泡降序排序,找出符合条件最大的k个值,优先删除派单尾数最少的区域中的派送人员,如果派单尾数相同,则在分配到派送人员数最多的区域中去掉一个派单人员,因此是一个双关键字排序算法。(3)样题给出数据的尾单数均不为0,因此条件b[i][1]%rs!=0始终成立,是否缩进不影响结果,只有当尾单出现为0时,影响结果。16.学校物品室有n个箱子(箱子上分别有编号1、2、3…n),箱子里存有数量不一的物品。有m位学生前来领取物品(物品总量足够领取),每位学生优先从物品数量最多的箱子领取,数量不够时,再从下一个数量最多的箱子领取。小郑设计了一个程序,按箱子编号从小到大依次输入每个箱子的物品数量,依次输入每位学生需要领取物品的数量,按顺序显示每个学生领取物品的箱子编号,并显示领取结束后非空箱子的编号和剩余物品数量。运行界面如图所示。物品数量:[12,9,5,5,3,2]箱子编号:[4,2,1,6,5,3]领取数量:[20,6,7,2]第1位学生领取物品的箱子编号依次为:4 2第2位学生领取物品的箱子编号依次为:1 6第3位学生领取物品的箱子编号依次为:6 5第4位学生领取物品的箱子编号依次为:3剩余物品数量:2号箱子:1回答下面问题:(1)如果1号到5号箱子的物品数量分别是25,16,9,5,3,每位学生需要的物品数量分别是19,18,10,3,则第3位学生领取物品的箱子编号按顺序依次是3号、________(填整数)号。(2)实现上述功能的程序如下,请在划线处填入合适的代码。#依次输入物品数量存入列表a,箱子上的编号(1 到 n)依次存入列表bh,箱子数量存入变量 n,并按物品数量从多到少对箱子排序,代码略。#依次输入学生需要领取物品的数量存入数组 b,学生人数存入变量 m,代码略p=0;q=0for i in range(m):num=0while numnum+=a[q]a[q]=0①________________s=″第″+str(i+1)+″位学生领取物品的箱子编号依次为:″for j in range(p,q):s+=str(bh[j])+″″print(s)if num>b[i]:a[q-1]=②________________q=q-1for j in range(③________________): #维护非空箱子降序序列(按箱子中剩余物品数量)if a[j] a[j],a[j+1]=a[j+1],a[j] bh[j],bh[j+1]=bh[j+1],bh[j]p=qs=″剩余物品数量:″for i in range(0,n):if a[i]>0: s=s+str(bh[i])+″号箱子:″+str(a[i])print(s)答案 (1)1 (2)①q=q+1 ②num-b[i] ③q,n-1解析 (1)第1位学生在1号箱子里领取19,第2位学生在2号中领取16,在3号中领取2。剩下箱子中数量依次为6,0,7,5,3,因此第3位同学领取3号箱子和1号箱子。(2)循环for i in range(m)中,变量i表示第几个学生,他应该领取的数量为按物品数量b[i],变量num表示他已经领取的数量,当条件num>b[i]成立时,②num-b[i]。③从多到少对箱子排序,比较对象为a[j]和a[j+1],因此从位置q到n-2,当j=n-2时,j+1达到终点。课时3 数据排序课时目标1.通过具体实例,理解排序的概念和基本方法。2.能根据实际的应用场景,选择合理的数据结构,并使用排序算法来编程解决问题。1.排序(1)排序的概念排序是指将一些________的数据变成________的数据。(2)排序方式排序方式主要有:________(从小到大排列)和________(从大到小排列)。(3)待排数据的存储方式待排数据通常存储在数组或链表中。2.常见的排序算法常见的排序方法有:____________、__________、插入排序、二叉树排序、快速排序、堆排序、归并排序和桶排序等。3.利用Python的sort方法和内建函数sorted排序(1)sort方法说明:使用sort方法对列表中的数据进行排序时,将____________对列表进行排序,不会产生________列表。例:列表lista=[36,23,12,17,22,19,28],可用命令lista.sort()将列表lista中的数据进行升序排序,可用命令lista.sort(reverse=True) 将列表lista中的数据进行降序排序。(2)sorted函数说明:使用sorted函数进行排序时,将排好序的数据返回一个____________。例:lista=[36,23,12,17,22,19,28],执行语句listb=sorted(lista)后,列表listb中的元素为[12,17,19,22,23,28,36,],从而实现升序排序;执行语句listc=sorted(lista,resverse=True)后,列表listc中的元素为[36,28,23,22,19,17,12],从而实现降序排序。4.冒泡排序(1)冒泡排序的基本思想冒泡排序是在数列中对________两个数据依次进行________和位置调整,让较大的数“下沉(或上冒)”,较小的数据“上冒(或下沉)”的一种排序技术。(2)冒泡排序的特点①________两个数据进行比较。②n个数据完成排序,共进行________趟(遍)排序。③n个数据完成排序,数据的比较次数为。④n个数据完成排序,其时间复杂度为________。5.冒泡排序算法的程序实现说明:对列表list1中的数据进行升序排序def bubble_sort(list1):count=len(list1)#count个数排序共需进行count-1趟for i in range(1,count):#每一趟排序从前往后进行,比较相邻两个数for j in range(0,count-i): if list1[j]>list1[j+1]: list1[j],list1[j+1]=list1[j+1],list1[j]return list1(1)冒泡排序进行时,数据的比较可以由前往后进行,即list1[j]与listl[j+1]比较;也可以由后往前进行,即list1[j]与list1[j-1]比较,此时应将循环条件“for j in range(0,count-i):”修改为“for j in range(count-1,i-1,-1):”。(2)若要将数据按降序排列,只需将语句“if list1[j]>list1[j+1]:”修改为“if list1[j]例1 采用冒泡排序算法对数据序列“21,15,23,26,33,18,46,17”完成升序排序,理论上讲共需进行排序的遍数为( )A.3遍 B.4遍 C.7遍 D.8遍听课笔记: 变式训练 采用冒泡排序算法对数据序列“16,11,8,9,21,32,28”完成升序排序,共进行数据交换的次数为( )A.3次 B.4次 C.5次 D.6次例2 采用冒泡排序算法对8个数据“48,65,29,16,22,75,36,41”进行降序排序,则第3遍的排序结果是( )原始数据 48,65,29,16,22,75,36,41第1遍完成后的数据为 75,48,65,29,16,22,41,36第2遍完成后的数据为 75,65,48,41,29,16,22,36第3遍完成后的数据为A.75,65,48,41,36,29,16,22B.75,65,48,41,29,16,22,36C.75,65,48,41,36,29,22,16D.75,65,48,41,29,22,16,36听课笔记: 变式训练 小明对6个数字“3,5,8,2,6,1”进行两遍冒泡排序后的数字序列设置为办公室门的密码锁,则该密码可能是( )①1 2 3 5 8 6 ②8 6 3 5 2 1 ③1 2 3 5 6 8④3 2 5 1 6 8 ⑤8 5 6 3 2 1A.①②③④⑤ B.①② C.④⑤ D.①②④⑤例3 列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:n=8for i in range(1,n-1): for j in range(1,n-i-1): if s[j]>s[j-1]: s[j],s[j-1]=s[j-1],s[j]该程序段实现的是( )A.s[0]到s[5]的降序排列 B.s[1]到s[6]的降序排列C.s[1]到s[7]的升序排列 D.s[2]到s[6]的升序排列听课笔记: 变式训练 有如下Python程序段:b=[17,8,6,15,21,36,18,33]n=len(b)for i in range(1,4):for j in range(n-1,i-1,-1):if b[j]>b[j-1]: b[j],b[j-1]=b[j-1],b[j]经过该程序段“加工”后,列表b中的元素为( )A.[36,33,17,8,6,15,21,18]B.[36,33,21,17,15,8,6,18]C.[36,33,21,17,8,6,15,18]D.[36,33,21,18,17,8,6,15]例4 小明编写程序实现数据排序功能,部分程序如下:n=len(d)for i in range(1,n): for j in range(n-i-1,-1,-1): if d[j]>d[j+1]: d[j],d[j+1]=d[j+1],d[j]print(d)此程序存在问题,不适合作为测试数据的是( )A.d=[9,6,5,8] B.d=[9,8,6,5]C.d=[8,9,5,6] D.d=[6,5,9,8]听课笔记: 变式训练 有如下Python程序段:d=[12,8,6,3,8,10]i=0;q=0;flag=Falsewhile i flag=True for j in range(len(d)-1,q,-1): : d[j],d[j-1]=d[j-1],d[j] q=j flag=False i=i+1程序运行后,加框处语句执行次数为( )A.15 B.12 C.9 D.81.采用冒泡排序算法对数据序列“9,7,6,8,5,4,2,3”进行升序排序,约定从前往后进行数据比较及位置交换,则第2趟排序结束时的数据序列为( )A.7,6,8,5,4,2,3,9 B.6,7,5,4,2,3,8,9C.6,5,4,2,3,7,8,9 D.6,7,4,2,3,5,8,92.采用冒泡排序算法对数据序列“6,8,9,5,4,2,7,3”进行降序排序,约定从后往前进行数据比较及位置交换,则进行第2趟排序时的数据交换次数为( )A.0次 B.1次 C.2次 D.3次3.有如下Python程序段:b=[99,88,77,66,55,61,71,81]count=len(b)for i in range(1,4):for j in range(0,count-i): if b[j]>b[j+1]: b[j],b[j+1]=b[j+1],b[j]经过该程序段“加工”后,列表b中的元素为( )A.[77,66,55,61,71,81,88,99]B.[55,61,66,71,77,81,88,99]C.[66,55,61,71,77,81,88,99]D.[66,61,55,71,77,81,88,99]4.有如下Python程序段:s=[2,3,8,7,5]for i in range(len(s)-1): for j in range(len(s)-1,i,-1): if s[j] 执行该程序段,加框处语句被执行的次数是( )A.3 B.6 C.8 D.105.有如下Python程序段:from random import randinta=[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+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]6.有如下Python程序段:s=″ccbbac″a=[i for i in range(6)]for i in range(5): for j in range(5-i): if s[a[j]]>s[a[j+1]]: a[j],a[j+1]=a[j+1],a[j]print(a)运行该程序段输出的结果为( )A.[4,3,2,5,1,0] B.[4,5,3,2,1,0]C.[4,2,3,0,1,5] D.[4,3,2,5,0,1]7.有如下Python程序:a=[1,5,2,9,6,7]n=len(a)for i in range(n∥2): for j in range(n-1,i,-1):if a[j]>a[j-1]: a[j],a[j-1]=a[j-1],a[j]执行该程序段后,a的值是( )A.[9,7,6,1,5,2] B.[9,7,6,5,2,1]C.[1,2,5,6,7,9] D.[9,6,7,5,2,1]8.有如下Python程序段:L=[21,12,13,17,16,15,20,28,11]def shengxu(a,b):for i in range(0,b-a):for j in range(__________): if L[j]>L[j+1]: L[j],L[j+1]=L[j+1],L[j]shengxu(3,7)print(L)若要实现列表L中L[a]到L[b]之间的数升序排列(不改变其余元素的位置),划线处的代码应为( )A.i,b B.0,b-iC.a,b-i D.b-1,a-i-1,-19.有如下Python程序段:a=[3,8,6,2,1,0,7]n=len(a)for i in range((n-1)∥2): j=0;k=1 while j if a[j]*k>a[j+2]*k: a[j],a[j+2]=a[j+2],a[j] j=j+1;k=-k执行该程序段,则a[4:7]的值为( )A.6,0,7 B.6,7,8 C.3,8,1 D.6,8,7课时3 数据排序知识梳理1.(1)无序 有序 (2)升序 降序2.冒泡排序 选择排序3.(1)直接 新的 (2)新的序列4.(1)相邻 比较 (2)①相邻 ②n-1 ④O(n2)5.0,count-i list1[j]>list1[j+1]例题精析例1 C [共有8个数据,共需要进行7遍排序, 因此答案为C。]变式训练 D [本题主要考查的是冒泡排序思想。排序过程如下:原始数据 16,11,8,9,21,32,28 交换次数第1遍完成后的数据为 8,16,11,9,21,28,32 交换3次第2遍完成后的数据为 8,9,16,11,21,28,32 交换2次第3遍完成后的数据为 8,9,11,16,21,28,32 交换1次第4遍完成后的数据为 8,9,11,16,21,28,32 不交换… … 不交换因此,完成升序排序,共交换的次数为6次,答案为D。]例2 A [本题主要考查的是冒泡排序的实现。根据第1、2遍可知,冒泡排序是从后往前进行降序排序,根据第2遍的结果可推出第3遍的排序结果为75,65,48,41,36,29,16,22,因此,答案为A。]变式训练 D [本题主要考查的是冒泡排序思想。排序方式有升序和降序,排序的方向可以从前往后或从后往前,因此要分4种情况进行讨论分析。如果是升序排序,从前往后进行两遍后数据序列为②,从后往前进行两遍后数据序列为①;如果是降序排序,从前往后进行两遍后数据序列为⑤,从后往前进行两遍后数据序列为④。因此,①②④⑤都有可能,答案为D。]例3 A [本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1,5],条件s[j]>s[j-1]表示当后一个数大于前一个数时要发生交换,实现降序排列。参加排序元素仅s[0]~s[5]。]变式训练 C [本题主要考查的冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法进行降序排序3遍,数据比较是从后往前进行的,进行第1遍排序后的数据序列为[36,17,8,6,15,21,33,18],进行第2遍排序后的数据序列为[36,33,17,8,6,15,21,18],进行第3遍排序后的数据序列为[36,33,21,17,8,6,15,18],因此答案为C。]例4 D [实现从后往前冒泡升序排列,前面的数据先有序,但右端没有固定,每趟都在缩减,因此有些数是排不到的。AB选项排序后均为5,6,9,8,无序,可以检测。C选项排序后为5,8,9,6,无序,可以检测。D选项排序为升序,与正确算法结果相同,无法检测。]变式训练 C [程序实现从后往前降序排序,q记录有序数据的个数,第1趟比较了5次,第2趟比较了3次,d的值为[12,10,8,8,6,3],q的值为4,排序后,数据有序,第3趟只比较1次,数据无交换,结束排序,比较次数分别为5+3+1=9。]随堂检测1.B [第1趟排序结束时的数据序列为7,6,8,5,4,2,3,9,第2趟排序结束时的数据序列为6,7,5,4,2,3,8,9。 因此,答案为B。]2.C [第1趟排序结束时的数据序列为9,6,8,7,5,4,2,3,数据交换5次,第2趟排序结束时的数据序列为9,8,6,7,5,4,3,2,数据交换2次,因此答案为C。]3.C [本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法进行升序排序3遍,数据比较是从前往后进行的,第1遍排序后列表b中的元素为[88,77,66,55,61,71,81,99],第2遍排序后的数据序列为[77,66,55,61,71,81,88,99],第3遍排序后的数据序列为[66,55,61,71,77,81,88,99],因此答案为C。]4.A [加框处语句表示交换次数,从条件s[j]5.B [本题考查排序算法和随机数函数。首先列表a中的初始值是[1,10]内的5个随机数。key的取值只能是6、8、10、12。while循环会将key插入列表a的合适位置上,使得列表a的值非降序排列,因此选项A、C、D都是有可能的。]6.C [本题考查索引排序。数组a存储的0-5的索引位置,程序实现从前往后冒泡,当条件s[a[j]]>s[a[j+1]]成立时交换,实现升序排列,因此排序后的结果是abbccc,找到这些字母的索引位置。]7.A [从后往前冒泡,排了3趟。]8.C [外循环控制排序的次数,也与排序的区间位置有关。冒泡排序必须是一端固定,另一端随着排序的过程将不断地缩短。若从前往后冒泡,则排序的初值必须为a,第一趟排序的区间是最长的,此时i的值为0,最后位置为b,而j+1到过b时,j的值为b-1,若要取到b-1,则终值必须为b,结合i的值,终值为b-i。]9.A [当k为1时,a[j]>a[j+2]表示升序排序,k为-1时,降序排序;程序实现奇位升序,偶位降序排列。 展开更多...... 收起↑ 资源列表 第五章 课时3 数据排序 学案(含答案).docx 第五章 课时3 数据排序.pptx