5.3.1 数据排序 课件（27张PPT）

(共27张PPT)
5.3 数 据 排 序 (一)
——冒 泡 排 序
册 别：选择性必修1
学 科：高中信息技术(浙教版)
学习目标：
能理解冒泡排序的算法思想。
能合理选用数据结构，理清冒泡排序的范围与条件。
能用自然语言、流程图、Python语言描述冒泡排序算法。
能分析冒泡排序次数、比较次数和交换次数。
能掌握优化冒泡排序方法。
想一想：
给下列5位同学从低到高排好队
、
想一想：
给下列5位同学从低到高排好队
、
排序概念：
、
排序：就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。
排序前：
排序后：
数组形式存储
链表形式存储
体验：Python中，对列表排序的方法
一、列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列
二、内建函数sorted方法，返回一个新的序列，原来的序列依然存在
reverse=True降序
默认： reverse=False升序
冒泡排序[递增]的方法是
冒泡排序[Bubble Sort]
是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉”（“上冒”），较小的数“上冒”（“下沉”）的一种排序技术。
每一遍加工都是将本遍中最大的元素“下沉” 至本遍的底端位置
——从前往后，升序
每一遍加工都是将本遍中最小的元素像气泡一样“上浮” 至本遍的顶端位置
——从后往前，升序
冒泡排序：
第一遍（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-i
冒泡排序[递增]的方法是
对于n个元素，第一遍加工将最大元素下沉到第n个位置
对于剩下的n-1元素，反复使用该规则，直到最后余下两个元素进行比较和交换
冒泡排序完成
冒泡排序标准程序的流程图描述：
开始
i ← 1,L ← len(d)
i<=L-1
j=0
jd[j]>d[j+1]
j=j+1
输出已排序数组d
结束
i=i+1
互换d[j]与d[j+1]
是
是
是
否
否
否
（1）
（2）
（3）
冒泡排序（递增）
#参考教材P131
d=[12,5,23,6,2]
n=len(d)
#外循环i取1-n-1共n-1次处理
#内循环从前往后冒：起点0与1位置上的元素，终点每次处理后往前缩进1
#相邻两两比较后，大数往后冒，两数互换
for j in range(n-i):
for i in range(1，n):
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
print("排序后的列表",d)
用Python语言编写程序并调试
d=[5,3,7,8,1,9,2,6]
n=len(d)
i=0
while ij=0
while :
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
j+=1
i+=1
print（“排序后的列表”,d）
#外循环i取0至n-2共n-1次加工
#大数往后冒，两数互换
#内循环每趟从第一个与第二个元素比较开始
#升序
填一填：
假如我们实现从前往后冒泡的升序排列，请问划线处填什么？
jj+1
j
n-2-i n-1-i
填一填：
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(n-1):
for 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]d[j],d[j-1]=d[j-1],d[j]
#外循环i取0-n-2共n-1次加工
for i in range(n-1):
for j in range(n-1,i,-1):
j
j-1
n-2 n-1
每一趟起点
j
j-1
0 1
第一趟i=0
j
j-1
1 2
第二趟i=1
用Python语言编写程序并调试
d=[5,3,7,8,1,9,2,6]
print("排序前的列表：",d)
n=len(d)
i=0
while iwhile j>i-1:
if d[j]d[j],d[j+1]=d[j+1],d[j]
j-=1
i+=1
print（“排序后的列表:”,d）
#外循环i取0-n-2共n-1次加工
#大数往前冒，两数互换
#内循环从后往前冒
#降序
填一填：
j=n-2
假如我们实现从后往前冒泡的降序排列，请问划线处填什么？
n-2 n-1
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(n-1):
for j in range（ ）:
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
print（“排序后的列表”,d）
#小数往前冒，两数互换
#升序
填一填：
假如我们实现从后往前冒泡的升序排列，请问划线处填什么？
#外循环i取0-n-2共n-1次加工
#内循环从后往前冒
n-2,
n-2 n-1
i i+1
i-1,
-1
冒泡排序分析
比较次数 (最多) 交换次数 (最多) 执行时间
(时间复杂度)
冒泡
以n个数据为例（在没有优化的情况下）
对n个元素的数组，用冒泡法进行排序时，共需比较
次数：
O(n2)
(n-1)
+…+1=
+(n-2)
冒泡排序优化的常用形式
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 ifor j in range(n-i-1): #从前往后冒
c=c+1
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
flag=True #flag变量
i=i+1
print("排序后的列表",d)
print("从前往后冒泡排序趟数：",i,"，比较次数",c)
flag=False #flag变量
请问划线处填什么？
优化算法2：内层优化：缩小内层比较的范围
算法思想：
1、在每遍冒泡过程中，最后一次交换的是last与last-1位置的数，表明在last之前的相邻数据已有序，进行下一遍冒泡时无序区域设置为[last,n-1](从后往前为例)
2、在某一遍排序时没有数据交换，说明待排序数据已有序，冒泡排序在此遍后结束
冒泡排序的优化算法2(升序从后往前排序)
第1趟处理：
待排序区域是
[0,n-1]
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
1 2 5 6 12 9 11 10 16
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=8 1 2 5 6 12 9 11 10 16
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=7 1 2 5 6 12 9 10 11 16
st=7
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=6 1 2 5 6 12 9 10 11 16
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
j=5 1 2 5 6 9 12 10 11 16
st=5
j=4至j=1没有数据交换
下一趟的排序区域
[st,n-1]
冒泡排序的优化算法2
#算法思想：记下最后一次交换的是last与last-1位置的数，表明在last之前的相邻数据已有序，进行下一遍冒泡时无序区域设置为[last,n](从后往前为例)
a=[5,10,15,78,16,7,37,25]
;n=len(a);num=0 #num排序遍数
flag=True
while flag==True:
flag=False
for j in range(n-1,last,-1): #从后往前冒
if a[j]t=a[j];a[j]=a[j-1];a[j-1]=t
flag=True
num=num+1
if last==n-1: break
print（"排序后的数列为：",a）
print（"冒泡排序过程的加工遍数为：",num）
请问划线处填什么？
last=j
last=0
j
j-1
st st+1
下一趟终点
冒泡排序的优化算法3
双向冒泡排序
1、首先从后往前利用冒泡排序算法，两两比较，将最小数放到第一个a[0]
2、然后从前往后利用冒泡排序算法，两两比较，将最大数放到最后一个a[n-1]
3、再对其余的n-2个数进行上述1、2同样的操作，其结果是将次小数放到a[1]，次大数放到a[n-2]
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
112 22 5 6 12 9 11 10 16
第1趟的排序区域[0,n-1]
第2趟的排序区域[1,n-2]
……
冒泡排序的优化算法3
import random #双向冒泡升序
n=10;a=[0]*n
for i in range(n): #随机产生n个两位数在列表a中显示
a[i]=random.randint(10,99)
top =0;bottom =n-1 #双向冒泡升序开始
print("原始列表:",a)
num=0 #num统计加工次数
while top < bottom: #外循环控制加工处理趟数
for j in range(bottom,top,-1): #从后从前利用冒泡算法，两两比较，将最小数放到第一个a[0]
if a[j] t = a[j];a[j] = a[j - 1];a[j - 1] = t
#顶端点缩进一个
for j in range(top,bottom): #从前到后利用冒泡算法，两两比较，将最大数放到最后一个a[n-1]
if a[j] >a[j + 1]:
a[j],a[j+1] = a[j+1],a[j]
#底端缩进一个
num+=1 #双向冒泡升序1趟结束
print（排序后的数列为：",a)
print（冒泡排序过程的加工遍数为：",num)
请问划线处填什么？
top + = 1
bottom - =1
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
112 22 5 6 12 9 11 10 16
第1趟的排序区域[0,n-1]
第2趟的排序区域[1,n-2]
……
课堂小结
冒泡排序
算法思想 算法描述
从前往后冒
优化冒泡排序
程序实现
从后往前冒
升序/降序
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。(3=优秀，2=一般，1=仍需加油)
评分项 自我评价
会用sort与sorted函数 3 2 1
看交谊舞得出冒泡排序两个特点：相邻比较、起点相同 3 2 1
能自主学习教材并用自然语言、流程图描述冒泡排序算法 3 2 1
能够用Python语言描述冒泡排序算法 3 2 1
能独立完成从前往后/从后往前/升/降冒泡排序的程序实现 3 2 1
能总结出冒泡排序的比较/交换次数，优化算法 3 2 1
1、程序运行后的结果如下所示：
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(n-1):
for j in range(n-2, ):
if d[j]d[j],d[j+1]=d[j+1],d[j]
print("排序后的列表",d)
课后作业
参考答案：1、i-1,-1 2、d[j]给划线处填上合适的语句
2、程序运行后的结果如下所示：
d=[5,3,7,8,1,9,2,6]
n=len(d)
for i in range(1,n):
for j in range(n-1,i-1,-1):
if ：
d[j],d[j-1]=d[j-1],d[j]
print("排序后的列表",d)
3、程序运行后的结果如下所示：
a=[8,10,15,78,16,27,39,21]
print("待排序数列为：",a)
n=len(a); ;num=0
flag=True
while flag==True:
flag=False
for j in range(1,last+1) :
if a[j]t=a[j];a[j]=a[j-1];a[j-1]=t
last=j-1
flag=True
num=num+1
if last==0: break
print("排序后的数列为：",a)
print("冒泡排序过程的加工遍数为：",num)
4、默写从前往后升序冒泡排序程序，并上机调试。