5.3.2 排序算法的应用 课件（22张PPT）
文档属性
| 名称 | 5.3.2 排序算法的应用 课件（22张PPT） |  | |
| 格式 | pptx | ||
| 文件大小 | 989.1KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 浙教版（2019） | ||
| 科目 | 信息技术（信息科技） | ||
| 更新时间 | 2024-05-08 19:00:45 | ||
图片预览
文档简介
(共22张PPT)
5.3 数 据 排 序
—— 排序算法的应用
册 别：选择性必修1
学 科：高中信息技术（浙教版）
学习目标：
能对给定的文件中的数据进行抽象并建立模型。
能合理选用数据结构，设计排序算法。
能用Python语言编写具体的排序程序。
能自觉对学习生活具体问题抽象建模、设计算法并编写程序及调试程序，如：对成绩进行同分同名次排名、按排车辆考场等。
阅读教材P132-134，可根据个性学习暂停或加速播放课程。
想一想：
请你给下面的2022北京冬奥会金牌编制金牌排行榜。
（一）抽象与建模
问题：每个国家的信息是一条记录，包括编号、国家/地区、各奖牌数等数据项。
实践体验：Excel排序，对记录按关键字排序，并关注交换如何进行？
（一）抽象与建模
问题：每个国家的信息是一条记录，包括编号、国家/地区、各奖牌数等数据项。
实践体验：Excel排序，对记录按关键字排序，并关注交换如何进行？
比较的是金牌数，交换的是整条记录
排序前
排序后
（二）设计算法与数据结构
：
数据组织形式有两种，哪种更方便？
方法一是采用6个一维数组按列存储，即每个数组分别存储每个国家的编号、国家、各奖牌数等，如定义a数组存储表中26个国家的编号;
定义b数组存储表中26个国家的国家名称，其对应的值为[“中国”,”澳大利亚 ” ,”美国 ” ,”加拿大 ” , ”法国” ……]
定义c数组存储表中26个国家的金牌数量，其对应的值为[4,1,5,1,1,4,0,0,8,3……]；
定义d数组、e数组、f数组分别存银牌、铜牌、总数
a b c d e f
（二）设计算法与数据结构
数据组织形式有两种，哪种更方便？
方法二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如[1,中国,4,3,1,8]对应中国的相关信息。
金牌为索引值[2]的元素
import csv #数据读入
csvFile = open("jp.csv", "r“) #打开相应数据文件
reader = csv.reader(csvFile) #建立一个读入数据的对象
a = []
for item in reader:
csvFile.close()
for i in range(1,len(a)-1): #排序不包含第一行数据
for j in range(1,len(a)-i):
if :
csvFile2 = open(‘jp2.csv’,‘w’, newline=‘’) #数据写入
writer = csv.writer(csvFile2, dialect='excel‘)
for i in range(len(a)):
writer.writerow(a[i])
csvFile2.close()
(三）编写程序
2022北京冬奥会金牌编制金牌排行榜
（给划线处填上合适的语句）
(三）编写程序（填空并调试）：
#数据读入
import csv #导入csv模块
csvFile = open(“jp.csv”, “r”) #打开jp.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #jp.csv中的每一行为a列表一个元素,此元素为字符串
a.append(item)
csvFile.close() #关闭jp.csv数据文件
#冒泡排序
for i in range(1,len(a)-1): #排序不包含第一行数据
for j in range(1,len(a)-i):#从前往后冒泡排序
if int(a[j][2])a[j]，a[j+1] =a[j+1]，a[j] #当前记录与后一条记录交换位置
csvFile2 = open(‘jp2.csv’,‘w’, newline=‘’)#数据写入到jp2.csv中
writer = csv.writer(csvFile2, dialect='excel‘)
for i in range(len(a)):
writer.writerow(a[i])
csvFile2.close()
a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5]
a[1] 1 中国 4 3 1 8
(三）编写程序 （结果如下）：
jp.csv
jp2.csv
挑战实践：
请你给2022北京冬奥会金牌编制金牌排行榜添加上金牌名次，而且同分数同名次，如何继续编程实现？
金牌 名次
10
9
9
9
8
7
7
1
2
2
2
5
6
6
0
1
2
3
4
5
6
7
挑战实践：
请你给2022北京冬奥会金牌编制金牌排行榜添加上金牌名次，而且同分数同名次，如何继续编程实现？
#数据读入
import csv #导入csv模块
csvFile = open(“jp.csv”, “r”) #打开jp.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串csvFile.close() #关闭jp.csv数据文件
#冒泡排序
for i in range(1,len(a)-1): #排序不包含第一行数据（索引为0）
for j in range(1,len(a)-i):#从前往后冒泡排序
if int(a[j][2])a[j]，a[j+1] =a[j+1]，a[j] #当前记录与后一条记录交换位置
#数据写入到jp2.csv中
csvFile2 = open(‘jp2.csv’,‘w’, newline=‘’)
writer = csv.writer(csvFile2, dialect='excel‘)
for i in range(len(a)):
writer.writerow(a[i])
csvFile2.close()
for i in range(len(a)):
a[i].append('排名') #添加每行的‘排名’列
c=1 #同分同名开始，c用于统计同分数的个数
a[1][6]=‘1’#第一个国家第一名，注意数据类型
for i in range(2,len(a)):#从第二个国家至最后一个
if a[i][2]!=a[i-1][2]: #当前国家金牌数与前一个不等
a[i][6]=str(int(a[i-1][6])+c)
#当前国家名次是前一个国家名次+前一金牌同分数的个数
c=1 #当前国家分数个数c恢复初值1个
else: #当前国家金牌数与前一个相等
a[i][6]=a[i-1][6] #当前国家与前一个相同名次
c=c+1 #统计同分个数
索引值为0 1 2 3 4 5 索引值为6
编号 国家 金牌 银牌 铜牌 总数 排名
10 德国 8 5 1 14 1
挑战实践：（同分同名次结果）
jp.csv
jp2.csv
学习生活中的应用实践：
在刚刚结束的联盟考成绩统计中，请你帮忙编写程序，能统计各科总分，并按照总分从高到低排序，并添加上总分名次，而且同分数同名次，成绩文件为“联盟.csv”，大概有5000左右考生，最后输出到“联盟2.csv”文件中。
处理前的表格
处理后的表格
学习生活中的应用实践：
#数据读入
import csv #导入csv模块
s=[] #定义空列表s
file=open('联盟.csv','r') #打开联盟.csv数据文件
lines=csv.reader(file))#建立一个读入数据的对象lines
n=0
for item in lines: #每一行为s列表一个元素,此元素为字符串
s.append(item) #csv通过这种样式读入的数据为字符串
n=n+1
file.close#关闭联盟.csv数据文件
for i in range(n): #添加2列
s[i].append("总分")
s[i].append("名次")
for i in range(1,n): #求总分
x=0
for j in range(3,13):
x+=float(s[i][j]) #注意数据类型
s[i][13]=str(x)
学习生活中的应用实践：
#应用优化冒泡排序
i=1;ed=1;flag=True #内循环比较交换优化、外循环遍历次数优化
while i<=n-1 or flag==True: #排序不包含第一行数据（索引为0）
flag=False
for j in range(n-1,ed,-1):#从后往前冒泡排序
if float(s[j][13])>float(s[j-1][13]):#当前记录的总分比后一条记录少
s[j],s[j-1]=s[j-1],s[j] #当前记录与后一条记录交换位置
ed=j;flag=True
if ed==n-1 or flag==False:break #未交换或上次交换为最后1个元素，退出while循环
i+=1
#数据写入到联盟2.csv中
file2 = open('联盟2.csv','w', newline='') #数据写入
writer = csv.writer(file2, dialect='excel')
for i in range(len(s)):
writer.writerow(s[i])
file2.close()
c=1#同分同名开始，c用于统计同分数的个数
s[1][14]=‘1’第一个学生第一名，注意数据类型
for i in range(2,n):
if s[i][13]!=s[i-1][13]: #当前学生总分与前一个不等
s[i][14]=str(int(s[i-1][14])+c)
#当前学生名次是前一个学生名次+前一学生同分数的个数
c=1#当前学生分数个数c恢复初值1个
else: #当前学生总分与前一个相等
s[i][14]=s[i-1][14]#当前学生与前一个同名次
c=c+1 #统计同分个数
学习生活中的应用实践：
处理前的表格
处理后的表格
课堂小结
抽象与建模
编写程序并调试
排序算法程序实现
设计算法与数据结构
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能对jp.csv文件中的数据进行抽象并建立模型 3 2 1
能对jp.csv数据选用合适的数据结构，设计排序算法 3 2 1
能用Python语言编写具体的排序程序(联盟考成绩排名)。 3 2 1
能自觉将学习生活具体问题抽象建模、设计算法并编写程序及调试程序，如：对成绩进行同分同名次排名、排考场车辆等实际应用。 3 2 1
课后作业1：秋游安排车辆
某班家委会根据参加秋游的同学到达指定上车点时间和每位同学可以等待的时间信息，安排车辆接送参加秋游活动同学去秋游点白云山脚（考虑车子座位数量<=4人）。参加秋游活动同学到达上车点的时间和可以等待的时间用长度为7的字符串表示，例如out.txt中第一行“ 08:11 4 xixi”表示xixi同学当天8点11分到达上车点，最多等待4分钟(每个同学的等待时间都小于10)，那么最晚8点23分出发去秋游点(若8点23分刚到的同学也一同出发)。编写 Python 程序，统计接送n个参加秋游活动同学所需的最少车辆数。运行程序，显示所有同学提交的信息，数据已经按到达时间先后排列，程序运行结果显示所需的最少车辆数。
（1）若将图中最后1 行“08:16 2”数据改为“08:16 7”，请问需要 （ ）辆车接送？（填数字）
4
课后作业：秋游安排车辆
a=[];xz=4 #每辆车最多坐4人
b=[];c=[]
n=0 #常量初始化,n值后面另计
for line in open("out.txt","r"): #从文件time.txt中读取时间数据
a.append(line.strip("\n"))
n+=1
for i in range(n):
print(a[i])
print("读取out.txt文件结束,共",n,"条数据。")
print("参加秋游人数n=",n)
#排序
for i in range(len(a)-1):
for j in range(len(a)-1, #① ):
if #② ：
a[j],a[j-1]=a[j-1],a[j]
for i in range(n):
b.append(0);c.append(0)
b[i]=int(a[i][:2])*60+int(a[i][3:5])
c[i]=b[i]+int(a[i][6:8])
print(b[i],c[i])
tot=0;i=0;k=1
while it=c[i]
j=i+1
while jif b[j]<=t:
k+=1;j+=1
else:
break
if k==xz:k=0;break
i=j
# ③
for i in range(n):
print(a[i])
print("接送所有参加秋游同学最少需要",tot,"辆车")
① i,-1
② a[j]③ tot+=1
课后作业2：教材P134思考与练习
1.结合“奥运排行榜”的例子，分别编写程序满足下列要求：
（1）若数据以7个一维数组的形式存储。
（2）若将排序关键字改为“奖牌数”，并按升序排序。
import csv #数据读入
csvFile = open("jp.csv", "r") #打开相应数据文件
reader = csv.reader(csvFile) #建立一个读入数据的对象
a = [] ;b=[];c=[];d=[];e=[];f=[]
for item in reader:
a.append(item[0])
b.append(item[1])
c.append(item[2])
d.append(item[3])
e.append(item[4])
f.append(item[5])
csvFile.close()
for i in range(len(a)):
print (a[i],b[i],c[i],d[i],e[i],f[i])
for i in range(1,len(a)-1): #排序不包含第一行数据
for j in range(1,len(a)-i):
if int(c[j])a[j],a[j+1] =a[j+1],a[j]
b[j],b[j+1] =b[j+1],b[j]
c[j],c[j+1] =c[j+1],c[j]
d[j],d[j+1] =d[j+1],d[j]
e[j],e[j+1] =e[j+1],e[j]
f[j],f[j+1] =f[j+1],f[j]
for i in range(len(a)): #输出排序后的序列
print (a[i],b[i],c[i],d[i],e[i],f[i])
5.3 数 据 排 序
—— 排序算法的应用
册 别：选择性必修1
学 科：高中信息技术（浙教版）
学习目标：
能对给定的文件中的数据进行抽象并建立模型。
能合理选用数据结构，设计排序算法。
能用Python语言编写具体的排序程序。
能自觉对学习生活具体问题抽象建模、设计算法并编写程序及调试程序，如：对成绩进行同分同名次排名、按排车辆考场等。
阅读教材P132-134，可根据个性学习暂停或加速播放课程。
想一想：
请你给下面的2022北京冬奥会金牌编制金牌排行榜。
（一）抽象与建模
问题：每个国家的信息是一条记录，包括编号、国家/地区、各奖牌数等数据项。
实践体验：Excel排序，对记录按关键字排序，并关注交换如何进行？
（一）抽象与建模
问题：每个国家的信息是一条记录，包括编号、国家/地区、各奖牌数等数据项。
实践体验：Excel排序，对记录按关键字排序，并关注交换如何进行？
比较的是金牌数，交换的是整条记录
排序前
排序后
（二）设计算法与数据结构
：
数据组织形式有两种，哪种更方便？
方法一是采用6个一维数组按列存储，即每个数组分别存储每个国家的编号、国家、各奖牌数等，如定义a数组存储表中26个国家的编号;
定义b数组存储表中26个国家的国家名称，其对应的值为[“中国”,”澳大利亚 ” ,”美国 ” ,”加拿大 ” , ”法国” ……]
定义c数组存储表中26个国家的金牌数量，其对应的值为[4,1,5,1,1,4,0,0,8,3……]；
定义d数组、e数组、f数组分别存银牌、铜牌、总数
a b c d e f
（二）设计算法与数据结构
数据组织形式有两种，哪种更方便？
方法二是采用1个一维数组按行存储，每个数组元素对应某个国家的一条记录信息，如[1,中国,4,3,1,8]对应中国的相关信息。
金牌为索引值[2]的元素
import csv #数据读入
csvFile = open("jp.csv", "r“) #打开相应数据文件
reader = csv.reader(csvFile) #建立一个读入数据的对象
a = []
for item in reader:
csvFile.close()
for i in range(1,len(a)-1): #排序不包含第一行数据
for j in range(1,len(a)-i):
if :
csvFile2 = open(‘jp2.csv’,‘w’, newline=‘’) #数据写入
writer = csv.writer(csvFile2, dialect='excel‘)
for i in range(len(a)):
writer.writerow(a[i])
csvFile2.close()
(三）编写程序
2022北京冬奥会金牌编制金牌排行榜
（给划线处填上合适的语句）
(三）编写程序（填空并调试）：
#数据读入
import csv #导入csv模块
csvFile = open(“jp.csv”, “r”) #打开jp.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #jp.csv中的每一行为a列表一个元素,此元素为字符串
a.append(item)
csvFile.close() #关闭jp.csv数据文件
#冒泡排序
for i in range(1,len(a)-1): #排序不包含第一行数据
for j in range(1,len(a)-i):#从前往后冒泡排序
if int(a[j][2])
csvFile2 = open(‘jp2.csv’,‘w’, newline=‘’)#数据写入到jp2.csv中
writer = csv.writer(csvFile2, dialect='excel‘)
for i in range(len(a)):
writer.writerow(a[i])
csvFile2.close()
a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5]
a[1] 1 中国 4 3 1 8
(三）编写程序 （结果如下）：
jp.csv
jp2.csv
挑战实践：
请你给2022北京冬奥会金牌编制金牌排行榜添加上金牌名次，而且同分数同名次，如何继续编程实现？
金牌 名次
10
9
9
9
8
7
7
1
2
2
2
5
6
6
0
1
2
3
4
5
6
7
挑战实践：
请你给2022北京冬奥会金牌编制金牌排行榜添加上金牌名次，而且同分数同名次，如何继续编程实现？
#数据读入
import csv #导入csv模块
csvFile = open(“jp.csv”, “r”) #打开jp.csv数据文件
reader = csv.reader(csvFile)#建立一个读入数据的对象reader
a = [] #定义空列表a
for item in reader: #每一行为a列表一个元素,此元素为字符串
a.append(item) #csv通过这种样式读入的数据为字符串csvFile.close() #关闭jp.csv数据文件
#冒泡排序
for i in range(1,len(a)-1): #排序不包含第一行数据（索引为0）
for j in range(1,len(a)-i):#从前往后冒泡排序
if int(a[j][2])
#数据写入到jp2.csv中
csvFile2 = open(‘jp2.csv’,‘w’, newline=‘’)
writer = csv.writer(csvFile2, dialect='excel‘)
for i in range(len(a)):
writer.writerow(a[i])
csvFile2.close()
for i in range(len(a)):
a[i].append('排名') #添加每行的‘排名’列
c=1 #同分同名开始，c用于统计同分数的个数
a[1][6]=‘1’#第一个国家第一名，注意数据类型
for i in range(2,len(a)):#从第二个国家至最后一个
if a[i][2]!=a[i-1][2]: #当前国家金牌数与前一个不等
a[i][6]=str(int(a[i-1][6])+c)
#当前国家名次是前一个国家名次+前一金牌同分数的个数
c=1 #当前国家分数个数c恢复初值1个
else: #当前国家金牌数与前一个相等
a[i][6]=a[i-1][6] #当前国家与前一个相同名次
c=c+1 #统计同分个数
索引值为0 1 2 3 4 5 索引值为6
编号 国家 金牌 银牌 铜牌 总数 排名
10 德国 8 5 1 14 1
挑战实践：（同分同名次结果）
jp.csv
jp2.csv
学习生活中的应用实践：
在刚刚结束的联盟考成绩统计中，请你帮忙编写程序，能统计各科总分，并按照总分从高到低排序，并添加上总分名次，而且同分数同名次，成绩文件为“联盟.csv”，大概有5000左右考生，最后输出到“联盟2.csv”文件中。
处理前的表格
处理后的表格
学习生活中的应用实践：
#数据读入
import csv #导入csv模块
s=[] #定义空列表s
file=open('联盟.csv','r') #打开联盟.csv数据文件
lines=csv.reader(file))#建立一个读入数据的对象lines
n=0
for item in lines: #每一行为s列表一个元素,此元素为字符串
s.append(item) #csv通过这种样式读入的数据为字符串
n=n+1
file.close#关闭联盟.csv数据文件
for i in range(n): #添加2列
s[i].append("总分")
s[i].append("名次")
for i in range(1,n): #求总分
x=0
for j in range(3,13):
x+=float(s[i][j]) #注意数据类型
s[i][13]=str(x)
学习生活中的应用实践：
#应用优化冒泡排序
i=1;ed=1;flag=True #内循环比较交换优化、外循环遍历次数优化
while i<=n-1 or flag==True: #排序不包含第一行数据（索引为0）
flag=False
for j in range(n-1,ed,-1):#从后往前冒泡排序
if float(s[j][13])>float(s[j-1][13]):#当前记录的总分比后一条记录少
s[j],s[j-1]=s[j-1],s[j] #当前记录与后一条记录交换位置
ed=j;flag=True
if ed==n-1 or flag==False:break #未交换或上次交换为最后1个元素，退出while循环
i+=1
#数据写入到联盟2.csv中
file2 = open('联盟2.csv','w', newline='') #数据写入
writer = csv.writer(file2, dialect='excel')
for i in range(len(s)):
writer.writerow(s[i])
file2.close()
c=1#同分同名开始，c用于统计同分数的个数
s[1][14]=‘1’第一个学生第一名，注意数据类型
for i in range(2,n):
if s[i][13]!=s[i-1][13]: #当前学生总分与前一个不等
s[i][14]=str(int(s[i-1][14])+c)
#当前学生名次是前一个学生名次+前一学生同分数的个数
c=1#当前学生分数个数c恢复初值1个
else: #当前学生总分与前一个相等
s[i][14]=s[i-1][14]#当前学生与前一个同名次
c=c+1 #统计同分个数
学习生活中的应用实践：
处理前的表格
处理后的表格
课堂小结
抽象与建模
编写程序并调试
排序算法程序实现
设计算法与数据结构
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能对jp.csv文件中的数据进行抽象并建立模型 3 2 1
能对jp.csv数据选用合适的数据结构，设计排序算法 3 2 1
能用Python语言编写具体的排序程序(联盟考成绩排名)。 3 2 1
能自觉将学习生活具体问题抽象建模、设计算法并编写程序及调试程序，如：对成绩进行同分同名次排名、排考场车辆等实际应用。 3 2 1
课后作业1：秋游安排车辆
某班家委会根据参加秋游的同学到达指定上车点时间和每位同学可以等待的时间信息，安排车辆接送参加秋游活动同学去秋游点白云山脚（考虑车子座位数量<=4人）。参加秋游活动同学到达上车点的时间和可以等待的时间用长度为7的字符串表示，例如out.txt中第一行“ 08:11 4 xixi”表示xixi同学当天8点11分到达上车点，最多等待4分钟(每个同学的等待时间都小于10)，那么最晚8点23分出发去秋游点(若8点23分刚到的同学也一同出发)。编写 Python 程序，统计接送n个参加秋游活动同学所需的最少车辆数。运行程序，显示所有同学提交的信息，数据已经按到达时间先后排列，程序运行结果显示所需的最少车辆数。
（1）若将图中最后1 行“08:16 2”数据改为“08:16 7”，请问需要 （ ）辆车接送？（填数字）
4
课后作业：秋游安排车辆
a=[];xz=4 #每辆车最多坐4人
b=[];c=[]
n=0 #常量初始化,n值后面另计
for line in open("out.txt","r"): #从文件time.txt中读取时间数据
a.append(line.strip("\n"))
n+=1
for i in range(n):
print(a[i])
print("读取out.txt文件结束,共",n,"条数据。")
print("参加秋游人数n=",n)
#排序
for i in range(len(a)-1):
for j in range(len(a)-1, #① ):
if #② ：
a[j],a[j-1]=a[j-1],a[j]
for i in range(n):
b.append(0);c.append(0)
b[i]=int(a[i][:2])*60+int(a[i][3:5])
c[i]=b[i]+int(a[i][6:8])
print(b[i],c[i])
tot=0;i=0;k=1
while i
j=i+1
while j
k+=1;j+=1
else:
break
if k==xz:k=0;break
i=j
# ③
for i in range(n):
print(a[i])
print("接送所有参加秋游同学最少需要",tot,"辆车")
① i,-1
② a[j]
课后作业2：教材P134思考与练习
1.结合“奥运排行榜”的例子，分别编写程序满足下列要求：
（1）若数据以7个一维数组的形式存储。
（2）若将排序关键字改为“奖牌数”，并按升序排序。
import csv #数据读入
csvFile = open("jp.csv", "r") #打开相应数据文件
reader = csv.reader(csvFile) #建立一个读入数据的对象
a = [] ;b=[];c=[];d=[];e=[];f=[]
for item in reader:
a.append(item[0])
b.append(item[1])
c.append(item[2])
d.append(item[3])
e.append(item[4])
f.append(item[5])
csvFile.close()
for i in range(len(a)):
print (a[i],b[i],c[i],d[i],e[i],f[i])
for i in range(1,len(a)-1): #排序不包含第一行数据
for j in range(1,len(a)-i):
if int(c[j])
b[j],b[j+1] =b[j+1],b[j]
c[j],c[j+1] =c[j+1],c[j]
d[j],d[j+1] =d[j+1],d[j]
e[j],e[j+1] =e[j+1],e[j]
f[j],f[j+1] =f[j+1],f[j]
for i in range(len(a)): #输出排序后的序列
print (a[i],b[i],c[i],d[i],e[i],f[i])