高中信息技术浙教版 (2019)选修1 数据与数据结构5.3 数据排序一等奖ppt课件

这是一份高中信息技术浙教版 (2019)选修1 数据与数据结构5.3 数据排序一等奖ppt课件，共27页。PPT课件主要包含了学习目标，想一想，排序概念，冒泡排序，冒泡排序完成，冒泡排序递增，jn-1-i，内循环从前往后冒，jn-2，n-2n-1等内容，欢迎下载使用。

能理解冒泡排序的算法思想。
能合理选用数据结构，理清冒泡排序的范围与条件。
能用自然语言、流程图、Pythn语言描述冒泡排序算法。
能分析冒泡排序次数、比较次数和交换次数。
能掌握优化冒泡排序方法。
给下列5位同学从低到高排好队
排序：就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。
体验：Pythn中，对列表排序的方法
一、列表自带的srt方法，只适用于列表，直接对列表进行排序，不会产生新的序列
二、内建函数srted方法，返回一个新的序列，原来的序列依然存在
reverse=True降序默认： reverse=False升序
冒泡排序[递增]的方法是
冒泡排序[Bubble Srt]是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉”（“上冒”），较小的数“上冒”（“下沉”）的一种排序技术。
每一遍加工都是将本遍中最大的元素“下沉” 至本遍的底端位置 ——从前往后，升序
每一遍加工都是将本遍中最小的元素像气泡一样“上浮” 至本遍的顶端位置 ——从后往前，升序
第一遍（i=1)加工后，冒泡范围j :[0,n-1]，最后一个元素d[4]最大
第二遍（i=2)加工后，冒泡范围j :[0,n-2]，倒数第二个元素d[3]次大
第三遍（i=3)加工后，冒泡范围j :[0,n-3]，倒数第三个元素位置固定
第四遍（i=4)加工后，冒泡范围j :[0,n-4]，倒数第四个元素位置固定
对5(n)个元素数组d从前往后冒泡升序排序
关注1：每趟（第i遍）相邻（j与j+1位置)两两比较的起点
关注2：每趟（第i遍）相邻（j与j+1位置)两两比较的终点
对于n个元素，第一遍加工将最大元素下沉到第n个位置
对于剩下的n-1元素，反复使用该规则，直到最后余下两个元素进行比较和交换
冒泡排序标准程序的流程图描述：
i ← 1,L ← len(d)
d[j]>d[j+1]?
互换d[j]与d[j+1]
#参考教材P131d=[12,5,23,6,2]n=len(d)
#外循环i取1-n-1共n-1次处理
#内循环从前往后冒：起点0与1位置上的元素，终点每次处理后往前缩进1
#相邻两两比较后，大数往后冒，两数互换
fr j in range(n-i):
fr i in range(1，n):
if d[j]>d[j+1]: d[j],d[j+1]=d[j+1],d[j]
print("排序后的列表",d)
用Pythn语言编写程序并调试
d=[5,3,7,8,1,9,2,6]n=len(d)i=0while id[j+1]: d[j],d[j+1]=d[j+1],d[j] j+=1 i+=1print（“排序后的列表”,d）
#外循环i取0至n-2共n-1次加工
#大数往后冒，两数互换
#内循环每趟从第一个与第二个元素比较开始
假如我们实现从前往后冒泡的升序排列，请问划线处填什么？
d=[5,3,7,8,1,9,2,6]n=len(d)fr i in range(n-1): fr j in range(n-i-1): if : d[j],d[j+1]=d[j+1],d[j]print( “排序后的列表”,d)
# 外循环i取0-n-2共n-1次加工
#小数往后冒，两数互换
假如我们实现从前往后冒泡的降序排列，请问划线处填什么？
d[j]冒泡排序（从后往前升序）：
d=[5,3,7,8,1,9,2,6]n=len(d) print("排序后的列表",d)
#小数往前冒，升序排列
#内循环从后往前冒,每次都是从第n-1与n-2位置上元素比较开始,至第i个结束
if d[j]#外循环i取0-n-2共n-1次加工
fr i in range(n-1):
fr j in range(n-1,i,-1):
d=[5,3,7,8,1,9,2,6]print("排序前的列表：",d)n=len(d)i=0while ii-1: if d[j]#大数往前冒，两数互换
假如我们实现从后往前冒泡的降序排列，请问划线处填什么？
d=[5,3,7,8,1,9,2,6]n=len(d)fr i in range(n-1): fr j in range（ ）: if d[j]>d[j+1]: d[j],d[j+1]=d[j+1],d[j]print（“排序后的列表”,d）
#小数往前冒，两数互换
假如我们实现从后往前冒泡的升序排列，请问划线处填什么？
以n个数据为例（在没有优化的情况下）
对n个元素的数组，用冒泡法进行排序时，共需比较
冒泡排序优化的常用形式
1、外层优化：减少排序趟数2、内层优化：缩小内层比较的范围3、双向冒泡：一遍排序同时把最小最大的数排好
冒泡排序优化算法1:外层优化：排序遍数
算法思想：看有无交换，无交换代表数据已有序程序实现：设一个flag变量做标记
d=[5,3,7,8,1,9,2,6]print("原来列表",d)n=len(d);i=0;c=0;flag=True #flag变量while id[j+1]: d[j],d[j+1]=d[j+1],d[j] flag=True #flag变量 i=i+1print("排序后的列表",d)print("从前往后冒泡排序趟数：",i,"，比较次数",c)
flag=False #flag变量
优化算法2：内层优化：缩小内层比较的范围
算法思想：1、在每遍冒泡过程中，最后一次交换的是last与last-1位置的数，表明在last之前的相邻数据已有序，进行下一遍冒泡时无序区域设置为[last,n-1](从后往前为例)2、在某一遍排序时没有数据交换，说明待排序数据已有序，冒泡排序在此遍后结束
冒泡排序的优化算法2(升序从后往前排序)
第1趟处理：待排序区域是[0,n-1]
#算法思想：记下最后一次交换的是last与last-1位置的数，表明在last之前的相邻数据已有序，进行下一遍冒泡时无序区域设置为[last,n](从后往前为例)a=[5,10,15,78,16,7,37,25] ;n=len(a);num=0 #num排序遍数flag=Truewhile flag==True: flag=False fr j in range(n-1,last,-1): #从后往前冒 if a[j]双向冒泡排序1、首先从后往前利用冒泡排序算法，两两比较，将最小数放到第一个a[0]2、然后从前往后利用冒泡排序算法，两两比较，将最大数放到最后一个a[n-1]3、再对其余的n-2个数进行上述1、2同样的操作，其结果是将次小数放到a[1]，次大数放到a[n-2]
第1趟的排序区域[0,n-1]第2趟的排序区域[1,n-2]……
imprt randm #双向冒泡升序n=10;a=[0]*nfr i in range(n): #随机产生n个两位数在列表a中显示 a[i]=randm.randint(10,99)tp =0;bttm =n-1 #双向冒泡升序开始print("原始列表:",a)num=0 #num统计加工次数while tp < bttm: #外循环控制加工处理趟数 fr j in range(bttm,tp,-1): #从后从前利用冒泡算法，两两比较，将最小数放到第一个a[0] if a[j] a[j + 1]: a[j],a[j+1] = a[j+1],a[j] #底端缩进一个 num+=1 #双向冒泡升序1趟结束 print（排序后的数列为：",a) print（冒泡排序过程的加工遍数为：",num)
算法思想 算法描述
对自己的表现进行客观的评价，并思考后续完善的方向。(3=优秀，2=一般，1=仍需加油)