(共13张PPT)
一、复习
1、冒泡排序思路:小元素从根部逐次向上浮动
2、冒泡排序程序设计要点：（1）基本形：
For i = 1 To n-1
For j = n To i + 1 Step -1
If d(j) < d(j - 1) Then
t = p(i):p(i) = p(i - 1):p(i - 1) = t
End If
Next j
Next i 规律：从根部向上冒泡，先冒出最小，连续双循环，双循环变量值对角加一，循环体数值交换
2、冒泡排序程序设计要点
（2）冒泡排序程序的小小变形：
For j =2 to n
For i = n To j Step -1
If p(i) < p(i - 1) Then
k = p(i): p(i)=p(i - 1):p(i - 1) = k
Next i
Next j
规律：对角相等、数值交换。
思考：排前10个应怎样改程序？
3、冒泡排序的循环比较次数及优缺点
（1）、n个数冒泡排序的循环比较次数是(n-1)+(n-2)+…+3+2+1
（2）、 n个数冒泡排序的交换次数不定
（3）、冒泡排序的优点：算法简洁明了、便于编程实现。
（4）、冒泡排序的缺点：交换次数频繁，程序执行时间长。
二、选择排序
选择排序（递增）的思路是
先找出n个数中最小的数据（下标跟踪），与数组第一个元素中的数据交换位置
再在余下的n-1个元素中继续找最小的元素，与第二个元素中的数据交换位置
依次类推，直到排序结束。
对比:冒泡、选择排序的循环次数（即比较次数）相同，不同的是交换次数。
三、选择排序算法演示
第 1 遍 选择
27
36
32
18
d (1)
d (2)
d (3)
d (4)
j=2
k=1
27
36
32
18
j=3
k=1
27
36
32
18
j=4
k=j
18
36
32
27
k=1
For j=2 to 4
if d(k)>d(j) then k=j
Next j
If k不等于1时，交换d(1)和d(k)
交换d(1)与d(4)
第2遍选择
18
36
32
27
d (1)
d (2)
d (3)
d (4)
j=3
k=2
18
36
32
27
j=3
k=j
18
36
32
27
j=4
k=j
j=4
18
36
32
27
k=j
18
27
32
36
k=2
For j=3 to 4
if d(k)>d(j) then k=j
Next j
If k<>2 then 交换d(2)和d(k)
第3遍选择
18
27
32
36
d (1)
d (2)
d (3)
d (4)
j=4
k=3
k=3
For j=4 to 4
if d(k)>d(j) then k=j
Next j
If k<>3 then 交换d(3)和d(k)
四、算法分析
第1遍选择 ，j从2开始到4
k=1
For j=2 to 4
if d(k)>d(j) then k=j
Next j
If k<>1，交换d(1)和d(k)
k=2
For j=3 to 4
if d(k)>d(j) then k=j
Next j
If k<>2 then 交换d(2)和d(k)
第2遍选择 ，j从3开始到4
第3遍选择 ，j从4开始到4
k=3
For j=4 to 4
if d(k)>d(j) then k=j
Next j
If k<>3 then 交换d(3)和d(k)
用i来表示次数的变化
For i=1 to 3
K=i ‘因为循环变量的值在
循环体内不能随意改变
For j=i +1 to 4
五、程序实现
For i = 1 To n- 1 ‘选择第i个作为最小的数
k = i
For j = i + 1 To n '如果找到更小的，用k记住它的编号
If d(k) > d(j) Then k = j ‘注意：d(k)与d(j)比较
Next j
特点：平行加一，下标跟随，数值交换，小数上冒。
——选择排序基本形
If k <> i Then '如果最小的数所在的位置不是i，则交换
t = d(i)
d(i) = d(k)
d(k) =t '注意： d(k)与d(i)交换
End If
Next i
六、选择排序和冒泡排序的比较
交换次数 循环比较次数
冒泡 <=(n-1)*n/2 (n-1)+…+3+2+1
选择 <=n-1 (n-1)+…+3+2+1
以n个数据为例:(运行比较程序)
冒泡：从根部向上冒泡，逐个交换，先冒出最小，升序排序。
选择：从顶部向下找较小数的下标，找到最小的数再交换至前，升序排序。
选择排序是冒泡排序的改进。
七、选择排序的变形
For i= n To 2 Step -1
Max = i ‘选择第i个作为最大的数
For j = 1 To i-1 ‘如果找到更大的，用max记住它的编号
If d(Max) < d(j) Then Max = j ‘d(min)与d(j)比较
Next j
If Max <> i Then ‘如果最大的数所在的位置不是i，则交换
k = d(i)
d(i) = d(Max)
d(Max) = k ‘d(max)与d(i)交换
End If
Next I
特点：对角减一，下标跟随，数值交换，大数下沉。
八、复习题解
高考倒计时
P70例4、 P74例11、 P77第5题(共18张PPT)
冒 泡 排 序
经典算法之
排序:把杂乱无章的数据变为有序的数据的过程。 （递增或递减）
冒泡排序:把较小的数据逐次向上推移的一种排序技术。
如何实现将较小数逐次从下向上推移呢？
一、冒泡排序的思想：从最下面一个元素起，依次比较相邻的两个元素中的数据，将较小的数据调换到上面,小元素像气泡一样上浮。
二、冒泡排序的过程
设置数组变量：a (i)为牌的值（i=1、2、3、4、5)
1
2
3
4
5
数组变量a
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)1
2
3
4
5
第三轮冒泡过程
a(5)a(4)>a(3),不变
1
2
3
4
5
第四轮冒泡过程
a(5)>a(4),不变
当堂练习
1、对“648251”中的6个数码进行两轮冒泡排序后即为某游戏中数字密码锁的密码，该密码是（ ）
A）684521 B）462518
C）126485 D）864521
C
当堂练习
2、下表中的原始数据是一组学生的军训打靶成绩，若采用冒泡排序算法对其进行排序，则第3遍的排序结果是 。
原始数据 第一遍 第二遍 第三遍 第四遍
98 85 85 85
95 98 88 88
85 95 98 93
93 88 95 95
88 93 93 98
93
85
88
95
98
分析：如果要对有5个元素的数组进行排序，那么
1、要进行________轮冒泡
2、第一轮冒泡的时候它进行比较的范围是从_________到________
第2轮冒泡的时候呢？
是从__________到________
第3轮冒泡的时候呢？
是从__________到________
4
a(5)与a(4)
a(2) 与a(1)
a(5)与a(4)
a(3) 与a(2)
a(5)与a(4)
a(4)与a(3)
第4轮冒泡的时候呢？
是从__________到________
a(5)与a(4)
a(5)与a(4)
A(j)两数交换
Y
N
对有5个元素的数组进行冒泡排序流程图1
开始
i＝1
i<=4
冒泡
i=i+1
Y
N
Y
j=5
J>=
j=j-1
N
J>=i+1
流程图2
For i= 1 to 4
Next i
For j=5 to step -1
if a(j)t=a(j):a(j)=a(j-1):a(j-1)=t
end if
Next j
比较两个数，如果后面的数比前面的小，则交换
i=1
i=2
i=3
i=4
i=1
2
i=2
3
i=3
4
i=4
5
a(j)—a(j-1)
a(5)—a(4)
a(4)—a(3)
a(3)—a(2)
a(2)—a(1)
a(j)—a(j-1)
a(5)—a(4)
a(4)—a(3)
a(3)—a(2)
a(j)—a(j-1)
a(5)—a(4)
a(4)—a(3)
a(j)—a(j-1)
a(5)—a(4)
j=5 to 2
j=5 to 3
j=5 to 4
j=5 to 5
i+1
程序实现
提高：如果要对有n个元素的数组进行排序，那么
要进行________轮冒泡，其中
外循环变量i从 到 变化，
内循环变量j从 到 变化。
n-1
1
n-1
n
i+1
a(1)、a(2)、a(3)、…a(n-2)、a(n-1)、a(n)
For i= 1 to 4
For j= 5 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 演示已知五个数的冒泡排序VB程序
n-1
n
三、冒泡排序的程序实现
思考1：第一个循环改为For i=2 to n后，j怎样变呢？
思考2：if a(j)a(j-1) 后对排序结果有何影响呢？
四、小结：
1、冒泡排序：每次从最下面的元素开始，通过逐次往上比较，将较小的数向上推移
2、如果有n个数组的元素进行排序，则要进行n-1趟冒泡
…….
第n-1趟冒泡要经过1次比较
第一趟冒泡要经过n-1次比较
第二趟冒泡要经过n-2次比较
总计要经过:(n-1)+(n-2)+(n-3)+………+2+1次比较
五、复习题解
高考倒计时
P70例3、 P77第6题、P80第14题(共15张PPT)
1、对分查找的基本思想
对分查找的前提是数据已经有序（以递增为例），然后把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找的数在数组中的位置或数组已无法对分。
查找算法
10
15
17
18
22
27
35
45
48
52
65
67
72
85
97
98
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
下标
元素
数组d(i ):
I=1
J=16
M=fix((i+j)/2) =8
第1次比较：
Key>d(m)
查找范围应该
变成d(9)~d(16)
Key=52
我们用变量 I和J记录所要查找范围的起始和终止位置
2、对分查找的基本过程：
10
15
17
18
22
27
35
45
48
52
65
67
72
85
97
98
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
下标
元素
数组d( ):
I=8+1
J=16
M=fix((i+j)/2) =12
第2次比较：
Key查找范围应该
变成d(9)~d(11)
Key=52
我们用变量 I和J记录所要查找范围的起始和终止位置
10
15
17
18
22
27
35
45
48
52
65
67
72
85
97
98
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
下标
元素
I=9
J=12-1
M=fix((i+j)/2) =10
第3次比较：
Key=d(m)
找到了
Key=52
思考： 如果key=33,能找吗？那么至少需要比较几次？
（2）在规模为n的数组变量d中进行对分查找的流程图
未找到，输出结果：0
开始
I←1 ，j←n
i<=j
找到，输出结果：m
结束
N
Y
计算中点m← (i+j)\2
d(m)=key
D(m)i←m+1
j←m-1
Y
Y
N
N
3、当堂练习：利用对分查找,在某校报名参加学生会主席竞选的学号列表20080101、20080135、20080238、20080342、20080450、20080558、20080633、20080708、20080846、20080910中，查找学号为20080846学生的过程中，依次被访问到的学号是（ ）
（A）20080450、20080708、20080846
（B）20080450、20080708、20080910、20080846
（C）20080558、20080708、20080846
（D）20080558、20080708、20080910、20080846
4、对分查找的核心代码分析
Key = Val(Text1.Text)
i = 1
j = num
Do While i <= j
If d(M) = Key Then
Label1.Caption="在数组的"+Str(M)+"位置中"
Exit Sub
End If
If d(M) < Key Then
Else
End If
Loop
Label1.Caption = "在数组中没有找到" + Str(Key)
m = (i + j) \ 2
i = m + 1
j=m-1
这个语句还有其它写法吗
Int((i+j)/2)或fix((i+j)/2)
5、顺序查找
27
36
32
18
d (1)
d (2)
d (3)
d (4)
输入查找的元素值key=32
i=1
i=2
i=3
此时d(i)=key,数组中的第3个位置
如果输入查找的元素值key=22
i=1
i=2
i=3
i=4
i=5
27
36
32
18
d (1)
d (2)
d (3)
d (4)
此时i等于5,超过数组中元素个数,找不到
从数组d的第1个元素d(1)开始，依次判断各元素的值是否与查找键key的值相等。
（1）、过程
（2）顺序查找的流程图
开始
i 1
d(i)=key
i<=n
i i+1
未找到，输出结果：0
找到，输出结果：i
结束
Y
N
Y
N
（3）转化成程序
Private Sub Command2_Click() '顺序查找
Key = Val(Text2.Text)
For i = 1 To num
If d(i) = Key Then
Label2.Caption = "在数组的 " + Str(i) + " 位置中"
Exit For
End If
Next
If i = num + 1 Then
Label2.Caption = "在数组中没有找到" + Str(Key)
End If
End Sub
6、顺序与对分查找比较
是否需要
事先排序 平均查找次数
顺序查找 不需要 (n+1)/2
多
对分查找 需要 Log2n
少
例1：从中国上海到美国旧金山海底电缆共有15个接点。现在某接点发生故障，需及时修理，为了尽快断定故障发生点，一般至多需要检查接点的个数为 个。
点评：这种检查线路故障的方法，就是二分法的应用。二分法不仅可用于查找线路、水管、气管故障，还可以用于实验设计、资料查询，也是求解高次方程的常用方法。
7、对分查找算法的实际应用
例2：在26枚崭新的金币中，混入了一枚外表与它们完全相同的假币（重量比真金的略低），现在只有一台天平，请问你最多称 次就可以发现这枚假币？
分析：本题可以通过二分法的思想来处理这种对称的问题。
解：第一次各13枚称量，选出较轻一端的13枚，继续称；第二次两端各6枚，若平衡，则剩下一枚即为假币，否则选取出较轻的6枚继续称；第三次两端各3枚，选取出较轻的3枚继续称；第四次，两端各一枚，若不平衡，可找出假币，若平衡，则剩余的是假币，所以，最多只需称4次。
8、复习题解
高考倒计时：
P70例5、P75例12、
P77第8题、P81第15题