资源简介

(共14张PPT)
5.3数据排序
——冒泡排序
冒泡排序
冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。
算法思想
升序时：大则交换，使得从前向后比较时________下沉；
降序时：小则交换，使得从前向后比较时________下沉。
大数
小数
冒泡排序
29
36
39
38
44
36
29
39
38
44
36
39
29
38
44
36
39
38
29
44
36
39
38
44
29
②
①
③
④
初始值
第1遍加工
第1遍加工：
i：_____，j：_________。比较_____次，交换___次。
1
[0,n-2]
d[0]
d[1]
d[2]
d[3]
d[4]
d[j]与d[j+1]比较
4/n-1
4
冒泡排序
39
36
38
44
29
39
38
36
44
29
39
38
44
36
29
36
39
38
44
29
②
①
③
初始值
第2遍加工
第2遍加工：
i：_____，j：_________。比较____次，交换____次。
2
[0,n-3]
d[0]
d[1]
d[2]
d[3]
d[4]
d[j]与d[j+1]比较
3
3
冒泡排序
39
38
44
36
29
39
44
38
36
29
39
38
44
36
29
②
①
初始值
第3遍加工
第3遍加工：
i：_____，j：_________。比较____次，交换____次。
3
[0,n-4]
d[0]
d[1]
d[2]
d[3]
d[4]
d[j]与d[j+1]比较
2
1
冒泡排序
44
39
38
36
29
①
初始值
第4遍加工
第4遍加工：
i：_____，j：_________。比较____次，交换____次。
4
[0,n-5]
d[0]
d[1]
d[2]
d[3]
d[4]
d[j]与d[j+1]比较
1
1
39
44
38
36
29
冒泡排序
d=[29,36,39,38,44]
n=len(d)
for i in range(_________):#加工遍数
for j in range(________):#每遍加工范围
if d[j]___________________#交换
print(d)
确定数据加工遍数
确定每一遍加工的范围
相邻比较，逆则交换
1,n
0,n-i
d[j],d[j+1]=d[j+1],d[j]
冒泡排序小结
初始值
1遍加工：
比较4次
交换4次。
2遍加工：
比较3次
交换3次。
3遍加工：
比较2次，
交换1次。
4遍加工：
比较1次，
交换1次。
有比较不一定有交换。
交换次数<=比较次数
n个数据比较次数为
n个数据交换次数为
比较与交换
29
36
39
38
44
36
39
38
44
29
39
38
44
36
29
39
44
38
36
29
44
39
38
36
29
(n-1)+(n-2)+...+1=n*(n-1)/2
0——n*(n-1)/2
冒泡变式
d=[29,36,39,38,44]
for i in range(_________):#加工遍数
for j in range(________):#每遍加工范围
if d[j]___________________#交换
print(d)
i表示遍数 j表示数组下标
0
1
2
3
0,n-1
0,n-i-1
d[j],d[j+1]=d[j+1],d[j]
i的范围：______________
j的范围：______________
0—n-2
0—n-i-2
29
36
39
38
44
[0,n-2]
[0,n-3]
[0,n-4]
[0,n-5]
冒泡变式
思考：若想要实现n个数据从后往前降序排序该如何改写上述代码？
d=[29,36,39,38,44]
n=len(d)
for i in range(_________):#加工遍数
for j in range(________):#每遍加工范围
if d[j]___________________#交换
print(d)
i表示遍数 j表示数组下标
1
[0,n-2]
2
[0,n-3]
3
[0,n-4]
4
[0,n-5]
1,n
n-2,i-1,-1
d[j],d[j+1]=d[j+1],d[j]
i的范围：______________
j的范围：______________
[1,n-1]
[0,n-i-1]
冒泡优化
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]:
__________
d[j],d[j+1]=d[j+1],d[j]
if c==0：
__________
更新每一遍中交换次数的存储变量
用于统计每一遍中交换的次数
判断数据是否已经有序
c+=1
break
真题练习
10.列表 s 包含 8 个互不相等的元素,即 s[0],s[1],s[2],……,s[7]，有如下 Python 程序段：
n=8
for i in range(1,n-1): #加工遍数：___________
for j in range(1,n-i-1): #第一遍加工j的取值范围：__________
if s[j]>s[j-1]: #升序/降序：___________
s[j],s[j-1]=s[j-1],s[j] #交换
该程序段实现的是（ ）
A.s[0]到s[5]的降序排列 B.s[1]到 s[6]的降序排列
C.s[1]到s[7]的升序排列 D.s[2]到 s[6]的升序排列
n-2
[1,n-2)
降序
A
End
Thank you

展开更多......

收起↑