资源简介

(共37张PPT)
排序算法专题复习
教学目标：归并排序，选择排序，插入排序，冒泡排序的基础代码格式
教学难点：冒泡排序的优化
教学难点处理方案：例题剖析+逐层递进
我们学过的排序算法：
1.冒泡排序（首考已考，最重要）
2.选择排序（首考未考，但要会看基础代码）
3.插入排序（首考未考，地方卷喜欢考）
4.归并排序（首考已考，思想重要如链表合二归一就是归并排序的变式，地方卷几乎没考过）
由于冒泡排序我们已经做过很多题，我们倒着从最不熟悉的开始4，3，2，1
lst1,lst2各自已按首位“时间”升序排序，要把lst2归并到lst1中，使得lst1整体依然升序
4.归并排序23.1首考真题再现
def merge(lst1, lst2):
i = len(lst1) - 1
j = len(lst2) - 1
for t in range(len(lst2)):
lst1.append([0, 0, 0]) # 为lst1追加一个元素[0, 0, 0]
k = len(lst1) - 1
while j >= 0:
if i >= 0 and lst1[i][0] > lst2[j][0]:
lst1[k] = lst1[i]
i -= 1
else:
lst1[k] = lst2[j]
j -= 1
k -= 1
return lst1
4.归并排序23.1首考真题再现
问：while语句中循环体的执行次数？
A
3.插入排序
3.插入排序：习题集p68T1 1.【2022年6月宁波九校高二信息技术第11题】
1．有如下python程序段，运行该程序段后，列表a中的值可能是( )
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]0:
a[j] = a[j-1]; j=j-1
a[j] = k
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
a=[偶，奇，偶，奇，偶，奇]
0 1 2 3 4 5
D
2.经典选择排序的代码：
a = [3, 2, 5, 4, 1] # 经典选择排序
n=len(a)#找比i项小且最小的数的下标j赋值给k，然后a[i]和a[k]互换
for i in range(n-1):#i标记待排序区间左边界
k=i
for j in range(i+1,n):#扫描待排序区间，找最小值下标j，给k=j，用当前数a[i]和a[k]互换
if a[j] k=j
if k!=i:#若a[i]不是最小值则将最小值交换到下标为i的位置
a[i], a[k] = a[k], a[i]
数据变化过程如下：
[3, 2, 5, 4, 1]
[1, 2, 5, 4, 3]
[1, 2, 3, 4, 5]
练习1. 某 Python程序段如下 :
for i in range(2) :
k = i
for j in range( i+ 1 ,5) :
if a[j] > a[k] ; k = j
if i ! = k : t = a[i] ; a[i] = a[k] ; a[k] = t
数组元素 a[0] 到 a[4] 的数据依次为“10,41,75, 12,63”。则此程序运行完成后数组元素a[0] 到 a[4] 的数据依次是 ( )
A. 75, 63, 41, 12, 10 B. 10, 12, 41, 63, 75
C. 10, 12, 75, 41, 63 D. 75, 63, 10, 12, 41
D
练习2. 利用如下 Python程序段对列表 a其进行处理 :
a=[‘15’, ’2’, ’5’, ’43’, ’24’]
i=4
while i>0:
k=i
for j in range(i) :
if a[k] a[k] ,a[i] =a[i] ,a[k]
i=i- 1
print(a)
该程序段执行后输出的内容是 ( )
A. [’15’, ’2’, ’24’, ’43’, ’5’] B.[’5’, ’15’, ’2’, ’43’, ’24’]
C. [’5’, ’15’, ’2’, ’24’, ’43’] D. [’2’, ’5’, ’15’, ’24’, ’43’]
A
2023.03杭州地区（含周边）重点中学卷（双向选择排序，最小的向前换，最大的向后换）
小明利用“在线社团报名系统”收集了全校学生的社团报名信息，并将报名数据导出到“社团报名.xlsx”中，如第14题图1 所示。然后编写Python程序对报名数据进行处理，生成分别以班级名和社团名为文件名的Excel文件，以便分发给相应的社团指导老师和班主任。
第14题图1 第14题图2
（1）在对表格进行数据整理时发现，关于“Jacky.Y” 同学的记录可能存在的数据问题是__▲___（选填：A.数据缺失 B.数据异常 C.逻辑错误 D.数据格式不一致）。
（2）其中生成每个社团名单文件的过程是：先对报名数据按社团名称进行分类，并对选报同一社团的学生按班级进行升序排序,然后生成各个社团名单文件，如第14题图2所示。对应的程序代码如下，请在划线处填写合适的代码。
D
（2）其中生成每个社团名单文件的过程是：先对报名数据按社团名称进行分类，并对选报同一社团的学生按班级进行升序排序,然后生成各个社团名单文件，如第14题图2所示。对应的程序代码如下，请在划线处填写合适的代码。
import pandas as pd
def read_file(filename):
#读入报名数据的原始文件，并将表中的数据转换成列表，代码略
def save_file(a): #保存名单到相应社团的Excel电子表格文件
df = pd.DataFrame(a,columns=[“班级”，“姓名”，“选报社团”])
df.to_excel( ① +“.xlsx”,index=False)
a = read_file(“社团报名.xlsx”)
n = len(a)
# 按社团名（参照拼音的字母顺序）进行升序排序，代码略
# 统计各社团人数，存在列表rs中，rs=[[“滑板社”，36]，…]，代码略
① a[0][2] 或 df.at[0,“选报社团”] 或 df[“选报社团”][0]
s = 0
for i in range(len(rs)):
②
left,right = s, s+num-1
while left < right:
imin = imax = left
for k in range(left+1,right+1):
if a[k][0] < a[imin][0]:
imin = k
elif a[k][0] > a[imax][0]:
imax = k
if imin != left:
a[imin],a[left] = a[left],a[imin]
if imax == left:
③
if imax != right:
a[imax],a[right] = a[right],a[imax]
left = left + 1; right = right–1
④
s += num
num=rs[i][1]
imax = imin
save_file(a[s:s+num])
1：冒泡排序的基本思想
每一轮从第0位或len（a）-1开始，通过相邻元素的比较，将较大或较小的数向后或向前推移的排序技术。
由此会产生4种冒泡排序组合：
1、从前向后冒，大的往后跑，升序
2、从前向后冒，小的向后跑，降序
3、从后向前冒，大的向前跑，降序
4、从后向前冒，小的向前跑，升序
1、从前向后冒，大的往后跑，升序
a = [5, 2, 1, 4, 3] # 从前向后冒，大的往后跑,升序for i in range(1,len(a)): #外循环i控制冒泡轮数 for j in range(len(a)-i): #内循环j控制冒泡方向 if a[j]>a[j+1]: #前一项>后一项 a[j], a[j+1] = a[j+1], a[j] print(a)#监控数据变化
j=0或1小数开始，从前向后冒
j=len（a）-1大数开始，从后向前冒
2、从前向后冒，小的向后跑，降序
a = [5, 2, 1, 4, 3]for i in range(1,len(a)): #外循环i控制冒泡轮数 for j in range(len(a)-i): #内循环j控制冒泡方向 if a[j]j=0或1小数开始，从前向后冒
j=len（a）-1大数开始，从后向前冒
3、从后向前冒，小的向前跑，升序a = [5, 2, 1, 4, 3] for i in range(1,len(a)): for j in range(len(a)-1,i-1,-1): if a[j] 4、从后向前冒，大的向前跑，降序
a = [4, 2, 1, 5, 3]
for i in range(1,len(a)): for j in range(len(a)-1,i-1,-1): if a[j] >a[j-1]: a[j], a[j-1] = a[j-1], a[j]
外循环i和内循环j，合作控制冒泡的范围
2
len（a）-2
[4, 5, 3, 2, 1]
[5, 4, 2, 1, 3]
排序后：a = [5, 4, 3, 2, 1]
谁控制排序范围？
10.列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7]，有如下Python程序段：2023年1月首考第10题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]的升序排列
A
2023年1月首考第10题真题回顾
例1：　采用冒泡排序算法对某数据序列进行排序，经过第一轮排序后的结果是＂2，8，3，9，5，6，7＂，那么原数据序列不可能的是 (　　)
A．8，3，9，5，2，7，6 B．8，3，9，2，6，5，7
C．8，2，9，3，5，7，6 D．8，3，2，9，6，5，7
D
例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[j]a[j],a[j+1]=a[j+1],a[j]
A.[9,3,1,7,6,3]
C.[1,3,3,9,7,6]
B.[9,7,6,3,3,1]
D.[1,3,3,6,7,9]
B
外循环控制轮次，n个元素进行了n-1轮循环，说明已完成排序
内循环控制轮次，步长-1，从后往前，确定前面的数
后一个数比前一个数大，互换，大的往前
D
练习2：有如下Python程序段：
a=[6,7,5,3,8,4]
f=1
for i in range(2):
for j in range(4-2*i):
if a[j]*fa[j],a[j+2]=a[j+2]f=-f
print(a)
该程序段运行后，输出结果为（ ）
A.[8,3,6,4,5,7]
B.[3,4,5,6,7,8]
C.[5,7,6,4,8,3]
D.[6,4,8,7,5,3]
变量f作用控制升降
A
冒泡排序算法优化
a=[23,20,13,18,14,11]
x=y=z=0
n=len(a)
for i in range(1,n):
x+=1
for j in range(0,n-i):
y+=1
if a[j]z+=1
a[j],a[j+1]=a[j+1],a[j]
# 统计排序加工的遍数
# 统计排序的比较次数
# 统计排序的交换次数
#加工的遍数
#单遍两两比较的范围
#比较的方向
程序中的x、y、z有什么作用？
a=[23,20,13,18,14,11]
n=len(a)
for i in range(1,n):
c=0
for j in range(0,n-i,-1):
if d[j]c+=1
d[j],d[j+1]=d[j+1],d[j]
if c==0:
break
如果一次加工过程中没有发生数据交换说明数据已经有序。
更新每一遍中交换次数的存储变量
用于统计每一遍中交换的次数
判断数据是否已经有序
优化遍数
a=[23,20,13,18,14,11]
n=len(a)
for i in range(1,n):
flag=False
for j in range(0,n-i,-1):
if d[j]flag=True
d[j],d[j+1]=d[j+1],d[j]
if flag==False:
break
优化遍数
23.4嘉兴二模第10题
10.列表s中包含n个互不相等的元素，用Python 编程实现如下功能: s[0]到s[n-1]降序排序，当序列已经有序时结束排序，部分代码如下。n=len(s)for i in range(1,n): （1） for j in range( （2） ): if （3） : s[j],s[j-1]=s[j-1],s[j] flag = True if flag==False: break上述程序段中方框可选代码为: ①flag=True ②flag=False ③1,n-i+1 ④1,n-i ⑤s[j]s[j-1]，则（1）（2）（3）处代码依次为A.②④⑥ B.②③⑥ C.①④⑤ D.①③⑥

优化遍数
C
典例1
有如下Python程序段：
d=[173,172,169,178,183]
for i in range(1,len(d)):
c=0
for j in range(0,len(d)-i):
if d[j]>d[j+1]:
c+=1;d[j],d[j+1]=d[j+1],d[j]
if c==0:
break
print (i)
则程序运行之后，i的值为（ ）
A. 1 B. 2 C. 3 D. 4
注意：此优化会在人观察到有序后再做一遍！
（不超过n-1遍）
C
173 172 169 178 183
i=1 172 169 173 178 183
i=2 169 172 173 178 183
2次
1次
i=3 169 172 173 178 183
0次
优化遍数
例4：有如下python程序段：
a=[2,1,9,8,6,3]
cnt=0
for i in range(len(a)-1,0,-1):
flag=False
for j in range(i):
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
flag=True
cnt+=1
if not flag:
break
则程序运行结束后，变量cnt的值为 （ ）
A.3 B.4 C.5 D.6
B
典例
有如下Python程序段：
d=[173,172,169,178,183]
last=len(d)-1;s=0
for i in range(1,len(d)):
for j in range(0,last):
s+=1
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
last=j
print (s)
则程序运行之后，s的值为（ ）
A. 10 B. 8 C. 6 D. 5
D
列表格还原比较过程！
173 172 169 178 183 比较
last
j
172
173
169
172
169
优化加工范围
练习1：已知字符串数组a的原始数据为[“128”,“26”,“9”,“61”,“15”,“2”,“318”],为了对该数组进行排序操作，小美编写了如下Python程序：
for i in range(3):
for j in range(6,i+1,-1):
if a[j]a[j],a[j-1]=a[j-1]则程序运行后，数组a的值为（ ）
A.[“128”,“15”,“2”,“26”,“318”,“61”,“9”]
B.[“128”,“15”,“26”,“9”,“61”,“2”,“318”]
C.[“128”,“15”,“2”,“26”,“9”,“61”,“318”]
D.[“128”,“15”,“2”,“26”,“318”,“9”,“61”]
D
本题涉及到字符串比大小的问题
练习2：有如下Python程序段：
a=[6,7,5,3,8,4]
f=1
for i in range(2):
for j in range(4-2*i):
if a[j]*fa[j],a[j+2]=a[j+2]f=-f
print(a)
该程序段运行后，输出结果为（ ）
A.[8,3,6,4,5,7]
B.[3,4,5,6,7,8]
C.[5,7,6,4,8,3]
D.[6,4,8,7,5,3]
变量f作用控制升降
A
练习3.排序并去重。小美基于冒泡排序算法编写了一个Python程序，可以输出剔除重复数据后的升序排序结果。程序运行界面如图所示。
排序前：[2,4,6,2,8,5,7,8,6,4]
排序后：[2,4,5,6,7,8]
实现上述功能的Python程序如下，请在划线处填入合适的代码。
import random
n=10
a=[random.randint(1,9) for i in range(10)]
print(“排序前：”，a)
i,top=0,n-1
while ifor j in range(top,i,-1):
if _______________:
a[j],a[j-1]=a[j-1],a[j]
elif a[j]==a[j-1]:
a[j]=_______
top=top-1
i+=1
print(“排序后： ”，_______)
a[j]a[top]
a[0:top+1]
通过覆盖去除重复数
输出排序后的元素
本节课小结
归并，插入，选择冒泡排序代码复习
通过i，j变化了解此类题型解题的一般方法
通过引入变量对冒泡排序进行简单优化
n个数需要经过n-1轮冒泡才能完成整个排序过程。
比较次数：(n-1)+(n-2)+(n-3)……+1=n*(n-1)/2
交换次数为：0~n*(n-1)/2
谢谢

展开更多......

收起↑