资源简介

(共24张PPT)
冒泡排序复习
浙教版新教材(2019)《数据与数据结构》选择性必修1——冒泡排序复习
经典冒泡从后往前冒，以下演示从前往后冒
2 3 4 5 1 0
1
5
0
5
第一遍：比较5次，交换2次
经典冒泡从后往前冒，以下演示从前往后冒
2 3 4 1 0 5
第一遍：比较5次，交换2次
第二遍：比较4次，交换2次
1
4
0
4
经典冒泡从后往前冒，以下演示从前往后冒
2 3 1 0 4 5
第一遍：比较5次，交换2次
第二遍：比较4次，交换2次
3
1
3
0
第三遍：比较3次，交换2次
经典冒泡从后往前冒，以下演示从前往后冒
2 1 0 3 4 5
第一遍：比较5次，交换2次
第二遍：比较4次，交换2次
第三遍：比较3次，交换2次
2
1
2
0
第四遍：比较2次，交换2次
经典冒泡从后往前冒，以下演示从前往后冒
1 0 2 3 4 5
第一遍：比较5次，交换2次
第二遍：比较4次，交换2次
第三遍：比较3次，交换2次
第四遍：比较2次，交换2次
1
0
第五遍：比较1次，交换1次
经典冒泡：从前往后与从后往前，总比较次数和交换次数不变，排序遍数n-1
一、冒泡排序思想
排序遍数是？比较次数？交换次数？
1、2组从前往后冒
3、4组从后往前冒
一、冒泡排序思想
冒泡排序思想总结：
★ 升序：将后数小于前数的两个数进行交换；降序：将后数大于前数的两数进行交换
★ n个数最多进行 n-1 遍排序
★ 两数比较的次数为: n*(n-1)/2
★ 两数交换次数最多为： n*(n-1)/2
升序
核心代码
for i in range(0,n-1):
for j in range(n-1,i,-1)
if a[j]交换a[j]与a[j-1]
控制遍数为n-1遍即可
初值定，控制每遍冒泡方向和比较次数，一般为n-1/n-2或0,1。终值与i和前后项表达相关。
初值和终值不能换位置。
控制次序——后项<前项，交换，升序。表达方法a[j-1]或a[j+1],从j初值可得
二、冒泡排序程序实现(一维数组为例)
课
堂
练
习
7.
D
三、冒泡排序应用
观察d变量，有哪些特征？
三、冒泡排序应用
编程实现，以左图形式显示
三、冒泡排序应用1
编程实现，按总分高到低排序
三、冒泡排序应用2
编程实现，女生在前，男生在后，分别按降序排序
三、冒泡排序应用3
编程实现，男生在前，降序排序，女生在后，升序排序
三、冒泡排序应用3
还有哪些排序形式？
出现同分情况怎么处理？
只排男生或只排女生？(位置不变）
只排前三名
不改变原有顺序排序？
四、冒泡排序优化1——遍数优化
for i in range(1,len(d)):
flag=False
for j in range(0,len(d)-i):
if d[j]>d[j+1]:
flag=True
d[j],d[j+1]=d[j+1],d[j]
if flag==False：
break
标记是否存在交换变量flag，默认无序
有交换，则标记True
内循环结束如无交换，则表明有序
一、冒泡排序优化1——遍数优化
i=1 ; flag=False
While iflag=True
for j in range(0,len(d)-i):
if d[j]>d[j+1]:
flag=False
d[j],d[j+1]=d[j+1],d[j]
i+=1
not flag
课
堂
练
习
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
则程序运行之后，i的值为（ ）
A. 1 B. 2 C. 3 D. 4
c
d=[173,172,169,178,183]
for i in range(1,len(d)):
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]
则程序运行之后，c的值为（ ）
A. 10 B. 8 C. 5 D. 3
D
课
堂
练
习
2. 若冒泡排序在某一遍加工过程中没有数据交换，则说明数据已经有序，
优化程序段如下：
a=[58,36,23,97,77]
n=len(a) ; i=1 ; flag=True
while i<=4 and flag==True:
flag=Flase
for j in range(4,i-1,-1):
if a[j]>a[j-1]:
a[j],a[j-1]=a[j-1],a[j] ; flag=True
i+=1
数组元素a[0]到a[4]的值依次为“58,36,23,97,77”，经过该程序段“加工”后，变量i的值是___________。
4
四、冒泡排序优化2——范围优化
当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。
当某段数据某遍加工过程中未发生任何一次数据交换，说明该段数据已经有序，无需进一步加工，只需处理其后数据即可。
下次冒泡只需比较到最后记录的位置，因为前段有序。
四、冒泡排序优化2——范围优化
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程度段生成随机数组a并将其中的元素从小到大排序：
import random
a=[0]*10 ; i=0
x=random.randint(1,100)
while i<10：
if x not in a：
a[i]=x ; i=i+1
x=random.randint(1,100)
i=0
while i<9：
k=I ; i=9
for j in range(9,k,-1)：
if a[j]a[j],a[j-1]=a[j-1],a[j]
▲
print(a)
则划线处应填入的语句是（ ）
A.i=j-1
B.i=j+1
C.i=k-1
D.i=j
D
课
堂
练
习
谢谢配合
浙教版新教材(2019)《数据与数据结构》选择性必修1——冒泡排序复习

展开更多......

收起↑