高中信息技术浙教版(2019)选修1 第五章 课时3 数据排序(学案 课件,2份打包)

资源下载
  1. 二一教育资源

高中信息技术浙教版(2019)选修1 第五章 课时3 数据排序(学案 课件,2份打包)

资源简介

(共84张PPT)
课时3 数据排序
第五章 数据结构与算法
1.通过具体实例,理解排序的概念和基本方法。2.能根据实际的应用场景,选择合理的数据结构,并使用排序算法来编程解决问题。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
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-1
O(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 list1
0,count-i
list1[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,22
B.75,65,48,41,29,16,22,36
C.75,65,48,41,36,29,22,16
D.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 1
A.①②③④⑤ B.①②
C.④⑤ D.①②④⑤
解析 本题主要考查的是冒泡排序思想。排序方式有升序和降序,排序的方向可以从前往后或从后往前,因此要分4种情况进行讨论分析。如果是升序排序,从前往后进行两遍后数据序列为②,从后往前进行两遍后数据序列为①;如果是降序排序,从前往后进行两遍后数据序列为⑤,从后往前进行两遍后数据序列为④。因此,①②④⑤都有可能,答案为D。
D
例3 列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:
n=8
for 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程序段:
C
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]
解析 本题主要考查的冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法进行降序排序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=False
while 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
随堂检测
3
1.采用冒泡排序算法对数据序列“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,9
C.6,5,4,2,3,7,8,9 D.6,7,4,2,3,5,8,9
B
解析 第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程序段:
C
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]
解析 本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是:采用冒泡排序算法进行升序排序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.10
5.有如下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+1]=a[j]
    j-=1
   a[j+1]=key
B
A.[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-i
C.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=-k
A
执行该程序段,则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.2
B.48.5,50.5,52.1,60.8,61.3,65.6,70.2,80.8
C.48.5,50.5,52.1,60.8,65.6,70.2,80.8,61.3
D.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=0
while 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-1
D
该程序段执行后,下列说法正确的是(  )
A.数组a各元素的值是:6 8 9 17 19
B.变量 k 的值为 3
C.数组元素 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.整个加工过程总的交换次数为 21
B.该程序段执行后,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-1
for 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=True
if ex_flag:
break
print(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+1
s=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=0
for i in range(qyn) :
  ②________
  if b[i][1]%rs!=0:
  b[i][2]+=1
 s+=b[i][2]
k=s-psryn
i=0
while 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=0
for i in range(m):
num=0
while 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-1
for 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=q
s=″剩余物品数量:″
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,22
B.75,65,48,41,29,16,22,36
C.75,65,48,41,36,29,22,16
D.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 1
A.①②③④⑤ B.①② C.④⑤ D.①②④⑤
例3 列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:
n=8
for 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=False
while 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.8
1.采用冒泡排序算法对数据序列“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,9
C.6,5,4,2,3,7,8,9 D.6,7,4,2,3,5,8,9
2.采用冒泡排序算法对数据序列“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.10
5.有如下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+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-i
C.a,b-i D.b-1,a-i-1,-1
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=-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时,降序排序;程序实现奇位升序,偶位降序排列。

展开更多......

收起↑

资源列表