5.3数据排序——冒泡排序课件(共23张PPT)

(共23张PPT)
排序算法
——冒泡排序
元旦晚会中，“五行”5人小组预排演歌舞，节目阵型依据身高共会产生3套变化，在前期准备中，组长A需要先对组中5人依据身高数据进行从低到高的排队。
A
？
常见的排序算法有：
冒泡排序、选择排序、插入排序、快速排序、堆排序、归并排序、桶排序……
其中，冒泡排序如何实现？
冒泡排序
概念理解
1
阅读书本129页，请简述冒泡排序原理
尝试演练
2
A
冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”
冒泡排序
A
A
经过这一遍加工后，你能得出什么结论？
冒泡排序的特点
冒泡排序从前往后依次对比和调整后，后方逐渐有序
方向有序
每一遍加工使得一个数据一定有序
所以n个数据经过n-1遍加工就完全有序
加工遍数
有比较不一定有交换
比较次数固定，交换次数不一定
比较与交换
发现
冒泡排序（一遍）
程序实现
数据的存储：数组（连续）、链表（不连续）
数据的指向与表示
数据的比较与处理
用d数组存储身高数据
用d[0]表示第一人身高
d[1]表示第二人身高
d[2]表示第三人身高
……
还能怎么表示？
将d[j]与d[j+1]进行比较
用d[j]表示第j+1人身高
确定数据加工遍数
确定每一遍加工的范围
冒泡排序（一遍）
178 172 183 169 173
d
j
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
for j in range( ):
0,len(d)
第一遍完成后，数据是：
172 178 169 173 183
j在第二遍加工中如何变化？
-1
for i in range(1, ):
-i
len(d)
相邻两数进行比较
与要求不符，即交换
练一练
在d数据为：178,172,183,169,173的情况下：
1、请完整写出这5个数据冒泡排序每一遍加工的结果
2、请计算这5个数据在冒泡排序时的比较次数和交换次数
想一想、改一改
for i in range(1,len(d)):
for j in range(0,len(d)-i):
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
1、若希望从大到小（高到低）排序，程序应如何修改？
2、若从后往前实现冒泡，程序应如何修改？
小结
确定数据加工遍数
确定每一遍加工的范围
相邻两数进行比较
与要求不符，即交换
1、n个数据，执行n-1遍加工即有序
2、n个数据，冒泡排序执行n*(n-1)/2次比较，交换次数随数据情况而定
3、冒泡排序的时间复杂度是O(n**2)
4、会描述冒泡排序每一遍加工结果
PPT模板下载：www./moban/ 行业PPT模板：www./hangye/
节日PPT模板：www./jieri/ PPT素材下载：www./sucai/
PPT背景图片：www./beijing/ PPT图表下载：www./tubiao/
优秀PPT下载：www./xiazai/ PPT教程： www./powerpoint/
Word教程： www./word/ Excel教程：www./excel/
资料下载：www./ziliao/ PPT课件下载：www./kejian/
范文下载：www./fanwen/ 试卷下载：www./shiti/
教案下载：www./jiaoan/
字体下载：www./ziti/
作业：
1、完成5.5的A
2、冒泡排序是否有优化方式
排序算法
——冒泡排序的优化
写一写
请完整写出n个数据从前往后实现升序的冒泡排序算法
确定数据加工遍数
确定每一遍加工的范围
相邻两数进行比较
与要求不符，即交换
for i in range(1,len(d)):
for j in range(0,len(d)-i):
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
如何让计算机知道数据有序？
数据不完全有序，但部分有序，如何优化
双向冒泡是否能提高效率
你还有其他优化方案吗？
你有哪些优化方案？
优化遍数
for i in range(1,len(d)):
for j in range(0,len(d)-i):
if d[j]>d[j+1]:
d[j],d[j+1]=d[j+1],d[j]
？
应如何修改代码
如何让计算机知道数据已经有序？
当没有交换再发生时，数据有序
（本遍加工交换次数为0）
统计交换次数，做交换次数为0的判断
优化遍数
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
更新每一遍中交换次数的存储变量
用于统计每一遍中交换的次数
判断数据是否已经有序
练一练
有如下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
优化范围
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
？
应如何修改代码
当数据部分有序如何优化范围
明确范围
（如果没有交换再发生，则可确定部分有序）
修改j的范围
优化范围
last=len(d)-1
for i in range(1,len(d)):
c=0
for j in range(0,last):
if d[j]>d[j+1]:
c+=1;d[j],d[j+1]=d[j+1],d[j]
last=j
if c==0:
break
赋初值
用于更新待比较范围
练一练
有如下Python程序段：
d=[173,172,169,178,183]
last=len(d)-1;s=0
for i in range(1,len(d)):
c=0
for j in range(0,last):
s+=1
if d[j]>d[j+1]:
c+=1
d[j],d[j+1]=d[j+1],d[j]
last=j
if c==0:
break
print (s)
则程序运行之后，s的值为（ ）
A. 10 B. 8 C. 6 D. 5
D
列表格还原比较过程！
继续思考
冒泡变式
去重排序问题
在比较时有操作！
……
重要的是把握变量作用
奇偶排序问题
并非相邻两数比较！
双向冒泡问题
控制j的变化！
PPT模板下载：www./moban/ 行业PPT模板：www./hangye/
节日PPT模板：www./jieri/ PPT素材下载：www./sucai/
PPT背景图片：www./beijing/ PPT图表下载：www./tubiao/
优秀PPT下载：www./xiazai/ PPT教程： www./powerpoint/
Word教程： www./word/ Excel教程：www./excel/
资料下载：www./ziliao/ PPT课件下载：www./kejian/
范文下载：www./fanwen/ 试卷下载：www./shiti/
教案下载：www./jiaoan/
字体下载：www./ziti/
作业：
1、完成5.5的B
PPT模板下载：www./moban/ 行业PPT模板：www./hangye/
节日PPT模板：www./jieri/ PPT素材下载：www./sucai/
PPT背景图片：www./beijing/ PPT图表下载：www./tubiao/
优秀PPT下载：www./xiazai/ PPT教程： www./powerpoint/
Word教程： www./word/ Excel教程：www./excel/
资料下载：www./ziliao/ PPT课件下载：www./kejian/
范文下载：www./fanwen/ 试卷下载：www./shiti/
教案下载：www./jiaoan/
字体下载：www./ziti/
谢谢！