资源简介

(共22张PPT)
选择排序专题复习
选择排序的思想
1、在待排序的数据中找出最小（大）的数据，把它与第一个位置的数据进行交换。
2、在余下位置中在继续找出最小（大）的数据，把它与第二个位置的数据进行交换。
……
以此类推，直到所有的数据排列有序。
选择排序的过程（升序为例）
1 2 3 4 5
设置数组变量：a(i)为牌的值（i=1、2、3、4、5)
第一轮选择
1 2 3 4 5
K
a(K)K不变
a(K)>a(3),
K更新
a(K)>a(4),
K更新
a(K)K不变
比较过程结束，K<>1，a(K)和a(1)交换
第二轮选择
1 2 3 4 5
K
a(K)>a(3),
K更新
a(K)K不变
a(K)K不变
比较过程结束，K<>2，a(K)和a(2)交换
第三轮选择
1 2 3 4 5
K
a(K)>a(4),
K更新
a(K)K不变
比较过程结束，K<>3，a(K)和a(3)交换
第四轮选择
1 2 3 4 5
K
a(K)>a(5),
K更新
比较过程结束，K<>4，a(K)和a(4)交换
分析与总结
如果要对有5个元素的数组进行排序，那么
1、要进行______轮选择
2、第一轮选择，k的初值为 ，比较的范围从 到 ；
第二轮选择，k的初值为 ，比较的范围从 到 ；
第三轮选择，k的初值为 ，比较的范围从 到 ；
第四轮选择，k的初值为 ，比较的范围从 到 。
3、总比较次数 次，数据最多交换 次。
4、每轮选择有 位置发生数据交换。
4
1
2
3
4
2
5
3
5
4
5
5
5
3
10
4
两个或零个
1.有6位裁判为运动员评分，给出的分数分别为49,45,61,46,58,
57。采用选择排序算法对其进行排序，若完成第一遍排序时的结果为45,49,61,46,58,57，则完成第二遍排序时的结果为（ ）
A.45,61,49,46,58,57 B.45,58,57,49,61,46
C.45,46,61,49,58,57 D.45,58,49,46,61,57
2.有6个数据，经过选择排序第一遍交换后顺序为21,65,36,84,45,
72，则其原始数据不可能是（ ）
A.36,65,21,84,45,72 B.84,65,36,21,45,72
C.65,36,21,84,45,72 D.45,65,36,84,21,72
C
C
练习
提高
如果要对有n个元素的数组进行排序，那么
1、要进行______轮选择
2、第一轮选择，k的初值为 ，比较的范围从 到 ；
第二轮选择，k的初值为 ，比较的范围从 到 ；
第三轮选择，k的初值为 ，比较的范围从 到 ；
……
第n-1轮选择，k的初值为 ，比较的范围从 到 。
3、总比较次数 次，数据最多交换 次。
n-1
1
2
3
n-1
2
n
3
n
4
n
n
n
3
n(n-1)/2
n-1
选择排序程序实现（升序）
For i = 1 To n-1
k = i
For j = i + 1 To n
If a(k) > a(j) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
’外层循环控制选择轮数
’内层循环控制选择范围
’满足条件，两数交换
练习
3.有如下VB程序段：
For i = 1 To 4
k = i
For j = 5 To i + 1 Step -1
If a(j) < a(k) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
f(i) = True
End If
Next i
当数组元素a(1)到a(5)的值依次为“8,2,1,21,3”，数组f的初值均为False，执行该程序后，f数组元素的值为True的个数有( )个
A.1 B.2 C.3 D.4
C
思考
若要把数列排成降序数列，程序如何修改？
For i = 1 To n-1
k = i
For j = i + 1 To n
If a(k) < a(j) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
思考
若只需要寻找数组中最小的三个数，程序如何修改？
For i = 1 To 3
k = i
For j = i + 1 To n
If a(k) > a(j) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
思考
若只需要将数组P到Q位置的元素进行排序（1<=P<=Q<=N),程序如何修改？
For i = P To Q-1
k = i
For j = i + 1 To Q
If a(k) > a(j) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
数组元素a(1)到a(5)的值依次为“24，16, 45,77，33”，经过该程序段“加工”后，数组元素a(1)到a(5)的值依次为
A.16,24,33,45,77
B.16,24,45,77,33
C.16,24,33,77,45
D.77,45,33,24,16
4.有如下VB程序段：
For i = 1 To 3
k = i
For j = i + 1 To n-1
If a(k) > a(j) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
B
练习
5.有如下VB程序段：
Dim a(1 To 5) As Integer
For i = 1 To 5
a(i) = Int(Rnd * 25) * 2 + 1
Next i
For i = 1 To 2
k = i
For j = i + 1 To 5
If a(k) Mod 10 > a(j) Mod 10 Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
经过该程序段“加工”后，数组元素a(1)到a(5)的值可能为
A.41,23,33,45,77
B.31,42,23,47,33
C.35,15,29,27,25
D.1,23,31,25,13
C
练习
总结
IF语句条件表达式即为排序的条件，按照什么内容（关键字）排序，选择什么位置（最大或者最小）。
内层循环：循环变量范围控制参与排序元素的范围，全部参与还是部分参与。
外层循环：循环变量范围控制选择的轮数，完全选择还是部分选择。
每轮选择有两个或零个数位置交换。
程序变式一：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 4 5 6 8 9 9 10 15
排序后：
p = 1: q = n
Do While p < q
max = p: min = q
For i = p To q
If a(i) > a(max) Then max = i
If a(i) < a(min) Then min = i
Next i
t = a(max): a(max) = a(q): a(q) = t
If min = q Then min = max
t = a(min): a(min) = a(p): a(p) = t
p = p + 1: q = q - 1
Loop
程序变式二：
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 4 15 5 10 6 9 8 9
排序后：
temp = 1
For i = 1 To n-1
k = i
For j = i + 1 To n
If a(k)* temp > a(j) * temp Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
temp = - temp
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 - 2
k = i
For j = i + 2 To n Step 2
If a(j) > a(k) Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
变式扩展
数组a(1 to 8) 10 5 8 6 9 4 15 9
原序列：
数组a(1 to 8) 8 9 9 6 10 5 15 4
排序后：
For i = 1 To n - 2
k = i
temp = (-1) ^ (i + 1)
For j = i + 2 To n Step 2
If temp * (a(j) - a(k)) < 0 Then k = j
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
End If
Next i

展开更多......

收起↑