冒泡算法的分析与设计
P10-1
30.10.2020
h
第二讲：冒泡算法的分析与实现
课前回顾 冒泡实例 冒泡分析 冒泡实现 冒泡总结 巩固练习
P9-2
30.10.2020
h
2.1冒泡排序的实例
1.冒泡排序实例：
【从小到大】 42 36
28
23
第一轮： 23
42
36
28
第二轮： 23 28
42
36
第三轮： 23 28
temp = d(j) d(j) = d(j - 1) d(j - 1) = temp
交换d(j)和d(j-1)之间的 数据
End If Next j Next i
P9-9
30.10.2020
h
2.6冒泡算法总结与作业
算法总结
在要排序的一组数中，对当前还未排好序的范围内 的全部数，自（上）左而（下）右对相邻的两个数 依次进行比较和调整，让较大的数往右沉，较小的 往左（上）冒。即：每当两相邻的数比较后发现它 们的排序与排序要求相反时，就将它们互换。
36
42
P9-3
30.10.2020
h
2.1冒泡排序的实例
2. 冒泡实例总结：
For i=1 to n-1 在d(i)、d(i+1)、…d(n)中通 过位置互换最小数的存放在d(i)中；也就是 选第i小的数放到第i号位置。
对冒泡排序：若待排序的序列有n个记录， 那么最多进行n-1趟排序，最大比较次数为 n（n-1）/2 。
课后作业
课后习题2.1、2.6、2.9 实验课上机实现冒泡算法
P9-10
30.10.2020
h
P9-5
30.10.2020
h
2.3核心算法的实现
遍历N个数； 内层循环：
第i个数与剩下的n-i-1 个数做比较；
顺序不符：
temp=d(j)
d(j)=d(j-1)
d(j-1)=temp
即d(j)和d(j-1)之间
的数据交换。
P9-6
30.10.2020
h
2.5冒泡算法的实现
-7
30.10.2020
h
随堂练：冒泡算法填空
若将34，45，32，12，33从小到达冒泡排序， 那么排序过程中比较的次数有 5 次。 交换的次数有 9 次。
P9-8
30.10.2020
h
随堂练：冒泡算法填空
For i = 1 To n-1 '冒泡排序 递增
For j = n To i+1 step -1
If d(j) > d(j - 1) Then
P9-4
30.10.2020
h
2.2冒泡算法的分析
For i=1 to n-1
在d(i)、d(i+1)…d(n)中通过位置互换最小数 的存放在d(i)中。也就是选第i小的数放到第 i号位置
Next i
怎样把在d(i)、d(i+1)、…d(n)中通过位 置互换把这些数中的最小数的存放在d(i) 中?