资源简介

(共30张PPT)
冒泡排序专题复习
冒泡排序的思想
从最下面一个元素起，依次比较相邻的两个元素中的数据，将较小的数据调换到上面，小元素像气泡一样上浮。
如何实现将较小数逐次从下向上推移呢？
冒泡排序的过程
1 2 3 4 5
设置数组变量：a(i)为牌的值（i=1、2、3、4、5)
第一轮冒泡
1 2 3 4 5
a(5)>a(4)，
不交换
a(4)交换
a(3)a(2)第二轮冒泡
1 2 3 4 5
a(5)>a(4)，
不交换
a(4)>a(3)，
不交换
a(3)第三轮冒泡
1 2 3 4 5
a(5)>a(4)，
交换
a(4)不换
第四轮冒泡
1 2 3 4 5
a(5)交换
分析与总结
如果要对有5个元素的数组进行排序，那么
1、要进行______轮冒泡
2、第一轮冒泡，比较的范围从 到 ；
第二轮冒泡，比较的范围从 到 ；
第三轮冒泡，比较的范围从 到 ；
第四轮冒泡，比较的范围从 到 。
3、总比较次数 次，数据最多交换 次。
4
a(5)与a(4)
a(2)与a(1)
a(5)与a(4)
a(5)与a(4)
a(5)与a(4)
a(3)与a(2)
a(4)与a(3)
a(5)与a(4)
10
10
提高
如果要对有n个元素的数组进行排序，那么
1、要进行______轮冒泡
2、第一轮冒泡，比较的范围从 到 ；
第二轮冒泡，比较的范围从 到 ；
第三轮冒泡，比较的范围从 到 ；
……
第n-1轮冒泡，比较的范围从 到 。
3、总比较次数 次，数据最多交换 次。
a(2)与a(1)
a(3)与a(2)
n-1
a(n)与a(n-1)
a(n)与a(n-1)
a(n)与a(n-1)
a(n)与a(n-1)
a(n)与a(n-1)
a(4)与a(3)
n(n-1)/2
n(n-1)/2
冒泡排序程序实现
For i= 1 to n-1
For j= n to i+1 step -1
If a(j)t=a(j):a(j)=a(j-1):a(j-1)=t
End if
Next j
Next i
’外层循环控制冒泡轮数
’注意j的初值和终值
’满足条件，两数交换
1.用冒泡排序算法对一组学生的身高数据进行升序排序，已知第一遍排序结束后的数据序列为165，168，178，175，171，则下列选项中不可能是原始数据序列的是
A.165,178,175,168,171
B.178,165,168,171,175
C.168,178,175,165,171
D.168,178,175,171,165
B
思考：
若要把数列排成降序数列，程序如何修改？
For i = 1 To n - 1
For j = n To i + 1 Step -1
If Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
Next i
a(j)>a(j-1)
思考：
若从前往后实现大值“下沉”，程序如何修改？
For i = 1 To n - 1
For j =
If a(j) < a(j - 1) Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
Next i
2 to n-i+1
思考：
若从前往后实现大值“下沉”，程序如何修改？
For i = n To 2 step -1
For j =
If a(j) < a(j - 1) Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
Next i
2 to i
思考：
若把每一遍加工时数据比较位置改为j和j+1，程序如何修改？
For i = 1 To n - 1
For j =
If a(j) > a(j + 1) Then
t = a(j): a(j) = a(j + 1): a(j + 1) = t
End If
Next j
Next i
n-1 To i Step -1
思考：
若只需要寻找数组中最大的三个数，程序如何修改？
For i =
For j = n To i + 1 Step -1
If Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
List1.AddItem Str(a(i))
Next i
a(j)>a(j-1)
1 to 3
a(j-1)思考：
若只需要将数组x到y位置的元素进行排序（1<=x<=y<=n),程序如何修改？(考虑排序不同方向）
For i = 1 to y-x
For j = x+1 to y-i+1
If a(j) < a(j - 1) Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
Next i
y to x+i step -1
2.有如下VB程序段：
For i = 1 To 2
For j = 5 To i + 1 Step -1
If a(j) < a(j-1) Then
t = a(j): a(j) = a(j-1): a(j-1) = t
End If
Next j
Next i
数组元素a(1)到a(5)的值依次为“33，24，45,16,77”，经过该程序段“加工”后，数组元素a(1)到a(5)的值依次为
A.16,24,33,45,77
B.16,24,45,33,77 C.77,24,45,16,33
D.77,45,33,24,16
A
3.有如下VB程序段：
Dim a(1 To 6) As Integer
For i = 1 To 6
a(i) = Int(Rnd * 45) * 2 + 10
Next i
For i = 1 To 2
For j = 2 To 6 - i
If a(j) \ 10 > a(j - 1) \ 10 Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
Next i
执行完该程序段后，下列选项中，a(1)到a(6)各元素的值可能是
A.84,98,93,84,62,30
B.70,60,10,28,18,14 C.34,44,36,14,16,94
D.77,42,34,16,24,82
C
总结
IF语句条件表达式即为排序的条件，按照什么内容（关键字）排序，排成什么状态（升序或者降序）。
内层循环：循环变量范围控制参与排序元素的范围，全部参与还是部分参与，步长控制数据比较的方向，前面先有序还是后面先有序。
外层循环：循环变量范围控制冒泡的个数，完全冒泡还是部分冒泡。
程序优化：
n个数不一定需要冒n-1个泡才完全有序，比如数组“3，5，7，9，11，2”冒一个泡后就实现了完全有序。如何实现一旦发现数组数据已经有序程序就不再进行排序，从而提高程序效率？
思考：如何判断一个数组数据已经有序了？
flag = False: i = 1
Do While iflag = True
For j = n To i + 1 Step -1
If a(j) < a(j - 1) Then
t = a(j)
a(j) = a(j - 1)
a(j - 1) = t
flag = False
End If
Next j
i = i + 1
Loop
某一轮冒泡过程没有发生数据交换，则说明数组有序
4.有以下VB程序：
flag = True : i = 1: n = 6
Do While i<= n - 1 and flag = True
flag = False
For j = n To i + 1 Step -1
If a(j) < a(j - 1) Then
t = a(j)
a(j) = a(j - 1)
a(j - 1) = t
flag = True
End If
Next j
i = i + 1
Loop
有一数组a(1 to 6)，其数值分别为“45，39，78，37，93，64”，想要按照从小到大排序，执行完该程序段后，数据总比较次数和总交换次数分别是
A.9次和4次
B.9次和6次
C.12次和6次
D.15次和12次
C
程序变式一：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 4 5 6 8 9 9 10 15
排序后：
For i = 1 To n \ 2
For j = n - i + 1 To i + 1 Step -1
If a(j) < a(j - 1) Then t = a(j): a(j) = a(j - 1): a(j - 1) = t
Next j
For j = i + 2 To n - i + 1 Step 1
If a(j) < a(j - 1) Then t = a(j): a(j) = a(j - 1): a(j - 1) = t
Next j
Next i
变式扩展：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 4 5 6 8 9 9 10 15
排序后：
For i = 1 To n \ 2
For j = i + 1 To n – i + 1 Step 1
If a(j) < a(j - 1) Then t = a(j): a(j) = a(j - 1): a(j - 1) = t
Next j
For j = n - i To i + 1 Step -1
If a(j) < a(j - 1) Then t = a(j): a(j) = a(j - 1): a(j - 1) = t
Next j
Next i
变式扩展：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 4 6 9 10 15 9 8 5
排序后：
For i = 1 To n \ 2
For j = n - i + 1 To i + 1 Step -1
If a(j) < a(j - 1) Then t = a(j): a(j) = a(j - 1): a(j - 1) = t
Next j
For j = i + 1 To n - i
If a(j+1) >a(j) Then t = a(j): a(j) = a(j + 1): a(j + 1) = t
Next j
Next i
程序变式二：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 4 15 5 10 6 9 8 9
排序后：
k = 1
For i = 1 To n - 1
For j = n To i + 1 Step -1
If a(j)*k < a(j - 1)*k Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
k = - k
Next i
变式扩展：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 15 4 10 5 9 6 9 8
排序后：
k = 1
For i = 1 To n - 1
For j = n To i + 1 Step -1
If a(j)*k > a(j - 1)*k Then
t = a(j): a(j) = a(j - 1): a(j - 1) = t
End If
Next j
k = - k
Next i
程序变式三：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 8 4 9 5 10 6 15 9
排序后：
For i = 1 To (n – 1)\2
For j = 1 To n - 2 * i
If a(j) > a(j + 2) Then
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
Next j
Next i
变式扩展：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 15 4 10 5 9 6 8 9
排序后：
k = 1
For i = 1 To (n -1)\2
For j = 1 To n - 2 * i
If a(j) * k < a(j + 2) * k Then
t = a(j): a(j) = a(j + 2): a(j + 2) = t
End If
k = - k
Next j
Next i
5.有如下VB程序段：
k = 1
For i = 1 To 2
For j = 1 To 6 - 2 * i
If k * a(j) < k * a(j + 2) Then
t = a(j): a(j) = a(j + 2): a(j) = t
End If
k = -k
Next j
Next i
数组元素a(1 to 6)的初始 数值分别为“15，11，58，38，26，9”，执行完该程序段后，数据a元素的值分别是
A.58，9，26，11，15，38
B.58，38，26，11，15，9
C.15，38，26，11，58，9
D.58，38，26，15，11，9
A

展开更多......

收起↑