专题七 排序算法的程序实现
【考纲标准】
考试内容
考试要求
排序算法的程序实现：
①冒泡排序
②选择排序
c
1．(2018·4月浙江选考)有一组正整数，要求仅对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。
排序前
86
71
5
41
81
79
37
89
排序后
5
37
41
71
79
89
86
81
实现上述功能的VB程序如下，但加框处代码有误，请改正。
Const n ＝ 8
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, t As Integer
Dim flag As Boolean
′读取一组正整数，存储在数组a中，代码略
For i ＝ 1 To n － 1
′(1)
If IsPrime(a(k)) Then flag ＝ True Else flag ＝ False
For j ＝ i ＋ 1 To n
If IsPime(a(j)) Then
If Then ′(2)
k ＝ j
flag ＝ True
End If
End If
Next j
If k <> i Then
t ＝ a(k): a(k) ＝ a(i): a(i) ＝ t
End If
If Not flag Then Exit For ′Exit For表示退出循环
Next i
′依次输出排序后的数据。代码略
End Sub
Function IsPrime(m As Integer) As Boolean
′本函数判断m是否是素数：是素数返回值为True，不是素数返回值为False
′代码略
End Function
解析 交换两个数的语句出现在外循环中，说明是选择排序，变量k表示每趟排序中的最值，因此k的初值是i。题目是要求仅对其中的素数进行升序排序，因此比较的对象a(k)还要求是素数。
答案 (1)k＝i
(2)Not flag Or a(j)
或Not IsPrime(a(k)) Or a(j) 或Not flag Or flag And a(j) 或Not IsPrime(a(k)) Or IsPrime(a(k)) And a(j) 2．(2017·11月浙江选考)小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。
实现上述功能的VB代码如下，但加框处代码有错，请改正。
Const n＝10
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer，j As Integer，t As Integer
Dim bottom As Integer ′剔除重复数据后元素的个数
′获取排序前数据依次存储在数组a中，并在文本框Text1中显示。代码略
bottom＝n
i＝1
Do While i<＝bottom －1
For j＝bottom To i＋1 Step －1
If Then ′(1)
t＝a(j)：a(j)＝a(j－1)：a(j－1)＝t
ElseIf a(j)＝a(j－1) Then ′若相邻数据相等，进行剔除处理
′(2)
bottom＝bottom－1
End If
Next j
i＝i＋1
Loop
Text2.Text＝" "
For i＝1 To bottom
Text2.Text＝Text2.Text＋Str(a(i))
Next i
End Sub
解析 本题考核从后往前冒泡的算法思想。从后往前冒泡，前面的数据先有序，当两次比较的数据a(j－1)和a(j)中相等时，a(j－1)可能已经有序，因此用最后一个数据替换a(j)，同时数据的有效长度bottom少1个。
答案 (1)a(j)a(j) 或其他等价表达式
(2)a(j)＝a(bottom) 或其他等价语句
3．(2016·10月浙江省技术选考)小吴为了研究冒泡排序过程中数据的“移动”情况，编写了一个VB程序，功能如下：在列表框List1中显示排序前数据(存储在数组a中)，在文本框Text1中输入初始位置(即下标值)，单击“排序”按钮Command1后，在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况，排序后的数据显示在列表框List2中。程序运行界面如图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Dim a(1 To 8) As Integer
Dim n As Integer
Private Sub Form_Load()
a(1)＝30：a(2)＝47：a(3)＝30：a(4)＝72
a(5)＝70：a(6)＝23：a(7)＝99：a(8)＝24
n ＝ 8
For i ＝ 1 To 8
List1.AddItem a(i)
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer
Dim pos As Integer
Dim s As String
s ＝ Text1.Text
pos ＝ Val(Text1.Text)
For i ＝ 1 To n － 1
For j ＝ n To i ＋ 1 Step －1
If a(j) < a(j － 1) Then
′(1)
a(j－1)＝a(j)
a(j)＝k
′如果pos位置的数据参与交换，则更新pos值，记录pos变化位置
If pos ＝ j Then
pos ＝ j － 1
s ＝ s ＋ ”→” ＋ Str(pos)
′(2)
pos ＝ j
s ＝ s ＋ ”→” ＋ Str(pos)
End If
End If
Next j
Next i
Label1.Caption ＝ “位置变化情况：” ＋ s
For i ＝ 1 To n
List2.AddItem Str(a(i))
Next i
End Sub
解析 第一处改错实现的是两个变量的交换。交换变量a(j)和a(j－1)的值后，该两个元素数据位置发生变化，接下来判断这两个元素的下标是否和pos相同，如果pos和j相同，已经被交换到j－1位置，pos需要更新，否则如果pos和j－1相同，已经被交换到j位置，pos需要更新。
答案 (1)k ＝ a(j－1) (2)ElseIf pos ＝ j － 1 Then
1．排序的作用是把n个数据从小到大或从大到小重新排列，使得a(1)至a(n)中的数据有序。排序的方法有很多，重点掌握冒泡排序和选择排序。
2．n个数据一般需要经过n－1趟排序，变量i控制排序的趟数。第i趟的比较次数往往有n－i次。
3．变量j表示比较大小的元素位置，其中数组元素a(j－1)表示第j－1个位置的数组元素，他位于a(j)的前面第一个元素，a(j＋1)位于a(j)的后面第一个元素。
4．内部循环(j的循环)初值和终值决定了排序的区间和方向。如果初值大于终值，初值往往是n，表示从后往前向后排序，若j的初值小于终值，初值往往是1，表示从前往后排序。
考点1 从后往前冒泡排序
1．以n(n＝5)个元素从后往前冒泡升序排序为例，完成下列表格。
趟数
排序区间
第1次
第2次
第3次
第4次
j终值
比较次数
有序区间
j
j－1
j
j－1
j
j－1
j
j－1
i＝1
[1，n]
5
4
4
3
3
2
2
1
2
4
[1，1]
i＝2
[2，n]
5
4
4
3
3
2
3
3
[1，2]
i＝3
[3，n]
5
4
4
3
4
2
[1，3]
i＝4
[4，n]
5
4
5
1
[1，4]
①第i趟冒泡，把最大或最小的元素交换到第i位置，实现从第1个位置到第i个位置的元素有序。数组前面的元素先有序。
②第i趟排序的区间是[i，n]，因此每趟排序的比较的位置(j的初值)为n。
2．每趟排序的算法
第i趟的排序实现在区间[i，n]中，从第n个位置的数开始，依次与前面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j－1)，比较完后向前移动，直到j－1的位置到达最前面的位置i为止，此时j＝i＋1。实现区间[1，i]的数据有序。
3．若每趟交换的次数为0，表示所有数据均有序，可以提前结束排序算法。也可以记flag的状态为False，若发生交换，将flag的值修改为True，根据flag的值，也可以表示数据是否有序。
4．每趟排序实现了[1，i]之间的数据有序，因此下趟排序的区间为[i＋1，n]。记录第i趟排序最后一次交换的位置j，此时表示[1，j－1]已经有序，下趟排序的区间可以修改为[j，n]，当j大于i＋1时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。
5．核心代码
【例1】 小刘在研究n个数的冒泡排序算法时，发现可以从两个方面进行优化：
(1)在每遍冒泡过程中，若最后一次交换的是last与last－1位置的数，则last－1位置之前的相邻数据均已有序。进行下一遍冒泡时，无序区域设置为[last，n]。
(2)若在某一遍排序中没有数据交换，说明待排序数据都已经有序，冒泡排序过程可在此遍排序后终止。
小刘按上述方法编写的冒泡优化VB程序，功能如下：程序运行时生成100个随机整数存入数组a，并显示在列表框List1中。单击“排序”按钮Command1后，对数组a中的数据进行排序，排序后的数据显示在列表框List2中，排序过程中实际的冒泡遍数显示在标签Label3上。程序运行界面如图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Dim a(1 To 100) As Integer
Private Sub Form_Load()
′产生100个无重复的三随机整数，存入数组a并显示在列表框list1中
′代码略
End Sub
Private Sub Command1_Click()
Dim flag As Boolean, i As Integer, j As Integer
Dim t As Integer, n As Integer, last As Integer
n ＝ 0: last ＝ 1
flag ＝ True
Do While ′(1)
flag ＝ False
For ′(2)
If a(j) > a(j － 1) Then
t ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ t
last ＝ j－1
flag ＝ True ′有交换发生
End If
Next j
n ＝ n ＋ 1
Loop
For i ＝ 1 To 100
List2.AddItem Str(a(i))
Next i
Label3.Caption ＝ “本次排序的冒泡遍数为：” & Str(n)
End Sub
其中，方框(1)处应改正为________；
方框(2)处应改正为________。
解析 flag表示有无交换的标志，如果本趟中没有发生数据的交换，表示数据已经有序，flag ＝ True语句出现在交换模块中，有交换还要循环，因此循环的条件是flag ＝ True。每趟比较的结束位置是last ＋ 1，但从大到小的步长是－1。
答案 (1)flag (2)j＝100 to last－1 Step －1
【例2】 有如下程序段：
For i ＝ 1 To 5
For j ＝ 10 To i ＋ 2 Step －1
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)至a(10)的值分别为“3，17，2，14，15，6，7，18，9，4”，执行该程序段后，数组元素a(8)中的值为( )
A．3 B．4 C．15 D．17
解析 从比较对象a(j)和a(j－2)看，属于奇数位和偶数位分别进行升序排列，每趟有2个数据有序，因此只要进行n2趟排序。偶数位的数据有17,14,6,18,4，升序排列中第2大的数是17。
答案 D
【变式训练1】 有一组正整数，基于冒泡排序对其中的数进行升序排序。排序后奇数在前，偶数在后。排序示例如下
排序前
78
30
64
39
49
4
8
32
18
32
排序后
39
49
83
4
8
18
30
32
64
78
实现上述功能的VB程序如下，但加框处代码有误，请改正。
Const n ＝ 10
Dim d(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer
′读取一组正整数，存储在数组 d 中，代码略
i ＝ 1
Do While i <＝ n － 1
For j ＝ n To i ＋ 1 Step －1
If d(j) Mod 2 ＝ d(j － 1) Mod 2 Then
If Then ′(1)
t ＝ d(j): d(j) ＝ d(j － 1): d(j － 1) ＝ t
End If
′(2)
t ＝ d(j): d(j) ＝ d(j － 1): d(j － 1) ＝ t
End If
Next j
i ＝ i ＋ 1
Loop
′依次输出排序后的数据，代码略
End Sub
解析 条件d(j) Mod 2 ＝ d(j － 1) Mod 2成立，表示相邻两个数都是奇数或都是偶数，相邻两个数进行比较，并且把小的数换到前面。如果是一奇一偶，且偶数在前，要把偶数换到后面。
答案 (1)a(j)考点2 从前往后冒泡排序
1．对称位置：在数组a(1)至a(n)中，有下列数组元素的位置是左右对称的，如a(1)与a(n)，a(2)与a(n－1)，a(3)与a(n－2)等，两个左右对称数组元素位置的下标之和是一个定值n＋1，因此可以到结论：与下标为i的数组元素左右对称的位置是n－i＋1。
2．以n(n＝5)个元素从前往后冒泡升序排序为例，完成下列表格。
趟数
排序区间
第1次
第2次
第3次
第4次
j终值
比较次数
有序区间
j
j＋1
j
j＋1
j
j＋1
j
j＋1
i＝1
[1，n]
1
2
2
3
3
4
4
5
4
4
[n，n]
i＝2
[1，n－1]
1
2
2
3
3
4
3
3
[n－1，n]
i＝3
[1，n－2]
1
2
2
3
2
2
[n－2，n]
i＝4
[1，n－3]
1
2
1
1
[n－3，n]
①第i趟冒泡，把最大或最小的元素交换到与他左右对称的位置n－i＋1的位置，实现从第n－i＋1个位置到第n个位置的元素有序。数组后面的元素先有序。
②第i趟排序的区间是[1，n－i＋1]，因此每趟排序的比较的位置(j的初值)为1。
3．每趟排序的算法
第i趟的排序实现在区间[1，n－i＋1]中，从第1个位置的数开始，依次与后面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j＋1)，比较完后向后移动，直到j＋1的位置到达最后面的位置n－i＋1为止，此时j＝ n－i。实现区间[n－i＋1，n]的数据有序。
4．每趟排序实现了[n－i＋1，n]之间的数据有序，因此下趟排序的区间为[1，n－i]。记录第i趟排序最后一次交换的位置j，此时表示[j＋1，n]已经有序，下趟排序的区间可以修改为[1，j]，当j小于n－i时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。
5．核心代码
优化前的代码
优化后的代码
i＝ 1
Do While i<＝n－1
j＝1
Do While j<＝n－i
If a(j) t＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝t
End If
j＝j＋1
Loop
i＝i＋1
Loop
flag＝True：bottom＝n－1
Do While flag＝True
j＝1：flag＝False
Do While j<＝ bottom
If a(j) t＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝t
p＝t : flag＝ True
End If
j＝j＋1
Loop
bottom＝p
Loop
【例3】 小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。
实现上述功能的VB程序如下，请将划线处填写完整。
Const n ＝ 10
Dim a(n) As Integer
Private Sub Form_Load()
′产生n个随机数，并显示在文本框Text1中，代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer
Dim top As Integer, s As String
top ＝ 1: i ＝ 1
Do While i <＝ n － 1
____①____
Do While j <＝ n － i
If a(j) > a(j ＋ 1) Then
t ＝ a(j): a(j) ＝ a(j ＋ 1): a(j ＋ 1) ＝ t
ElseIf a(j) ＝ a(j ＋ 1) Then
____②____
top ＝ top ＋ 1
End If
j ＝ j ＋ 1
Loop
i ＝ i ＋ 1
Loop
s ＝" "
For i ＝ top To n
s ＝ s ＋ Str(a(i))
Next i
Text2.Text ＝ s
End Sub
解析 从语句Do While j <＝ n－i来看，属于从前往后冒泡，比较的对象是a(j)和a(j＋1)，因此数据从后面开始有序，当两个数据是重复时，把开头的数据替换a(j)，继续排序，变量top表示不重复数据的开始位置，j的初值从top开始。
答案 ①j ＝ top ②a(j) ＝ a(top)
【变式训练2】 小赵对冒泡升序排列算法进行了如下改进：在一趟排序中，同时进行从最后一个元素向前的比较并交换和从第一个元素向后比较并交换，把最小的元素交接到前面，把最大的元素交换到后面，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序如下，但加框处代码有错，请改正。
Dim a(8) As Integer, i As Integer
Const n ＝ 8
Private Sub Command1_Click()
Dim j As Integer, start As Integer, last As Integer
start ＝ 1: last ＝ n
Do While start < last
For i ＝ ′(1)
If a(i) > a(i － 1) Then
t ＝ a(i): a(i) ＝ a(i － 1): a(i － 1) ＝ t
End If
Next i
start ＝ start ＋ 1
For i ＝ start ＋ 1 To last － 1
If a(i) < a(i ＋ 1) Then
t ＝ a(i): a(i) ＝ a(i ＋ 1): a(i ＋ 1) ＝ t
End If
Next i
′(2)
Loop
For i ＝ 1 To n
List2.AddItem Str(a(i))
Next i
End Sub
Private Sub Form_Load()
′产生8个随机数，并显示在列表框List1中，代码略
End Sub
解析 先用从后往前的冒泡排序，将小的数排到前面，再用从前往后冒泡排序的方法，把较大的数排序后面，直到所有数据有序。
答案 (1)last To start ＋ 1 Step －1 (2)last ＝ last － 1
考点3 选择排序
一、排序思想
在数据区间[i，n]范围内，查找最值的位置k，并把该位置的数与第i个数进行交换，使得[1，i]数据有序，重复执行n－1趟。该算法包括两个步骤，一是查找区间[i，n]中最值位置k，二是交换位置k与位置i上值。
二、算法实现
1．理解变量i、j和k的含义
变量i控制排序的趟数，n个数需要通过n－1趟(轮)排序；变量j表示比较大小的元素位置，k表示每趟中最大或最小数所在位置。
2．比较的方向和步骤
第i趟排序：在区间[i，n]中查找最值的位置k。每趟k的初值默认在第i个位置，因此比较的范围在[i＋1，n]，每次比较的位置j在最值k的后面。
3．以5个元素a(1)至a(5)选择排序升序为例。
趟数
排序
区域
k初值
k所在位置的最值与j所在位置的数组元素比较
比较次数
有序区域
第1次
第2次
第3次
第4次
j初值
i＝1
[1，n]
1
k→2
k→3
k→4
k→5
2
4
[1，1]
i＝2
[2，n]
2
k→3
k→4
k→5
3
3
[1，2]
i＝3
[3，n]
3
k→4
k→5
4
2
[1，3]
i＝4
[4，n]
4
k→5
5
1
[1，4]
①表示可以看出，第i趟排序的区间是[i，n]，因此比较位置j每次从i＋1开始，一直到最后，用最值k所在位置的数a(k)与a(j)，如果a(k)②在比较过程中，只是发生了k值的更新，而没有进行数据交换，即每趟最多只交换了一次。
③每趟数据是否交换的条件取决于k值是否发生了更新。
4．冒泡排序与选择排序的区别
排序
比较对象
交换情况
冒泡
相邻的两个数
比较后，逆序即交换，每趟可能交换多次
选择
最值与待排序区域的数
最值与第j个数交换，每趟最多交换一次
5.选择排序标准代码(在数组a中，以升序为例进行选择排序)：
For i＝1 To n－1 ′n个数共进行n－1趟排序
K＝i ′第i趟排序时，首先用k记录i
For j＝i＋1 To n ′k位置上的数依次与j位置上的数进行比较
If a(j) Next j
If k<>i Then ′若i位置上的数不是最小数，则和k位置上的数进行互换
temp＝a(i)：a(i)＝a(k)：a(k)＝temp
End If
Next i
【例4】 小赵对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：
p＝1：q＝10
Do While p < q
iMin ＝ p：iMax ＝ p
For i ＝ p ＋ 1 To q
If a(i) < a(iMin) Then iMin＝i
If a(i) > a(iMax) Then iMax＝i
Next i
t ＝ a(iMin): a(iMin) ＝ a(p): a(p) ＝ t
t ＝ a(iMax): a(iMax) ＝ a(q): a(q) ＝ t
p＝p＋1
q＝q－1
Loop
要使程序实现上述算法思想，则方框中的语句是( )
A．If iMax＝ p Then iMax ＝ iMin
B．If iMin＝ p Then iMin ＝ iMax
C．If iMax＝ p Then iMin ＝ iMax
D．If iMin＝ p Then iMax ＝ iMin
解析 该算法是对选择排序算法的改进，由原来的找到最大数(或最小数)后从一个方向排序改为从最小和最大两个方向同时进行排序；每趟排序a(iMin)为找到的最小数，a(iMax) 为找到的最大数；最小数a(iMin)和a(p)交换，排到前边，然后最大数a(iMax)和a(q)交换，排到后边，实现升序排列；在每一趟循环中，如果没有方框中的语句，在a(p)恰好为最大数a(iMax)(即imax＝p)时，因为最小数a(iMin)和a(p)先进行交换，交换后a(iMax)会变成最小数，a(iMax)和a(q)再进行交换会把最小数交换到a(q)而出现错误；方框中的语句应为避免这一错误的语句，A正确。分析程序时可以从待选项中获取线索。
答案 A
【变式训练3】 从数据库中读取各考生的编号、笔试和面试成绩，在文本框Text1中输入录取人数，按笔试与面试成绩之和从高到低录取，若成绩之和相等，面试成绩高的排前面。当录取人数达到计划录取人数时，若有面试加笔试的总分与之相等的分数，也要作为录取对象。程序运行的界面如图所示：
VB程序代码如下，但加框处的代码有错，请改正。
Const n ＝ 266
Dim ms(n) As Integer, bs(n) As Integer, bh(n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, s As String
For i ＝ 1 To n － 1
k ＝ i
For j ＝ i ＋ 1 To n
If ms(j) ＋ bs(j) > ms(k) ＋ bs(k) Then
k ＝ j
Then ′(1)
If ms(j) > ms(k) Then k ＝ j
End If
Next j
If k <> i Then
t ＝ ms(k): ms(k) ＝ ms(i): ms(i) ＝ t
t ＝ bs(k): bs(k) ＝ bs(i): bs(i) ＝ t
t ＝ bh(k): bh(k) ＝ bh(i): bh(i) ＝ t
End If
Next i
t ＝ Val(Text1.Text)
i ＝ 1
Do While i <＝ t Or ′(2)
s ＝ ”序” ＋ Str(i) ＋ ”：编号” ＋ Str(bh(i)) ＋ ” ”
s ＝ s ＋ Str(bs(i)) ＋ ”＋” ＋ Str(ms(i)) ＋ ”＝” ＋ Str(bs(i) ＋ ms(i))
List1.AddItem s
i ＝ i ＋ 1
Loop
End Sub
Private Sub Form_Load()
′从数据库中读取各考生的编号(bh数组)、笔试(bs数组)和面试(ms数组)成绩，分别存储在相应的数组中
End Sub
解析 第一部分为选择排序，有两种情况要交换，即总分大于前者，或者总分相等，但笔试高的，因此为多分支选择结构。第二部分为输出，输出的条件有两个，即输出的人数比计划录取人数少；或者已经达到计划录取人数，却还存在总分与计划录取最后一人的总分相等，也要输出。
答案 (1)ElseIf ms(j) ＋ bs(j) ＝ ms(k) ＋ bs(k)
(2)ms(i) ＋ bs(i) ＝ ms(i－1) ＋ bs(i －1)
一、选择题
1．有一个数组，采用冒泡排序，第一遍排序后的结果为：4，10，5，32，6，7，9，17，24该数组的原始顺序不可能的是( )
A．10，5，32，6，7，9，17，24，4
B．10，5，32，6，7，9，4，17，24
C．10，5，32，4，6，7，9，17，24
D．4，10，5，32，17，9，24，6，7
解析 从第一遍排序的结果来看，把到小的数交换到第1个位置，因此属于从后往前冒泡。
答案 D
2．有如下VB程序段：
For i ＝ 1 To 2
For j ＝ 5 To i ＋ 1 Step －1
If a(j) > a(i) Then
t ＝ a(j): a(j) ＝ a(i): a(i) ＝ t
End If
Next j
Next i
数组元素a(1)到a(5)的值依次为“33，24，45，16，77”，运行程序，数组元素a(1)到a(5)的值依次为( )
A．77，45，33，16，24 B．77，33，45，16，24
C．77，24，45，16，33 D．77，45，33，24，16
解析 该程序段中比较和交换的对象为a(j)和a(i)，因此不属于冒泡算法，可以采用分i＝1和i＝2两种情况进行讨论。当i＝1时，交换77和33，当i＝2时，交换33和24，再交换33和45。
答案 A
3．有如下VB程序段：
For i ＝ 1 To 2
For j ＝ 1 To 5－i
If a(j＋1)a(j＋1)＝t
Next j
Next i
数组a(1)到a(5)中数据分别为56，23，78，11，8，执行上述VB程序段后，数组元素的值分别为( )
A．8，11，23，56，78 B．23，11，8，56，78
C．11，8，23，56，78 D．8，11，56，23，78
解析 本题采用从前向后冒泡两趟的算法，a(j＋1)答案 B
4．有如下程序段：
Dim flag(0 To 4) As Boolean, p As Integer
For i ＝ 1 To 4
flag(i) ＝ False
Next i
i ＝ 1: flag(0)＝True
Do While i <＝ 4 And flag(i－1)
For j ＝ 5 To i ＋ 1 Step －1
If a(j) < a(j － 1) Then
k＝a(j)：a(j)＝a(j－1)：a(j－1)＝k
flag(i) ＝ True
End If
Next j
i ＝ i ＋ 1
Loop
数组元素a(1)到a(5)值依次为“16，4，24，33，77”，程序运行后，flag数组中为True个数及i的值分别是( )
A．1，2 B．1，3 C．2，2 D．2，3
解析 本题考核的是从后往前冒泡排序，语句flag(i) ＝ True表示如果有交换，那么第i趟的值为True。第1趟有交换，所以flag(1)为True，第2趟没有交换，在i＝3时，条件flag(i－1)＝True不成立。flag(0)和flag(1)为True。
答案 D
5．有如下VB程序段：
For i ＝ 1 To 2
For j ＝ 2 To 7 － i
If a(j) > a(j － 1) Then
k＝a(j)：a(j)＝a(j－1)：a(j－1)＝k
End If
Next j
Next i
数组元素a(1)到a(6)的值依次为“71，54，58，29，31，78”，运行程序，下列说法正确的是( )
A．数组元素a(1)到a(6)的值依次为54，29，31，58，71，78
B．此过程中数据共需比较次数为8次
C．此过程中数据共需交换次数为5次
D此过程中数据“54”共被比较5次
解析 该程序采用从前往后冒泡两次的算法的变式，比较对象是a(j)和a(j－1)，但j的初值是2。条件a(j) > a(j － 1)成立表示后面的比前面大交换，降序。比较次数为5＋4＝9次。交换次数为：第1趟，54和58，29分别和31、78交换，第2趟，31和78交换。
答案 D
6．有如下部分程序段：
a(1) ＝ ”20”： a(2) ＝ ”16”： a(3) ＝ ”12”： a(4) ＝ ”o”： a(5) ＝ ”k”
For i ＝ 1 To 4
For j ＝ 5 To i ＋ 1 Step －1
Ifa(j)>a(j－1)Thent＝a(j)：a(j)＝a(j－1)：a(j－1)＝t
Next j
List1.Additem a(i)
Next i
该程序段运行后，列表框List1中显示的内容为( )
A．12，16，20，o，k B．o，k，20，16
C．o，k，20，16，12 D．20，16，
解析 在字符比较中，先从左边第1个字符开始比较，数字小于大写字母小于小写字母，如果前面的字符相等，再继续往后比较。采用的是从后往前冒泡排序，但只显示前面4个数组元素。
答案 B
7．有如下VB程序段：
s ＝ ” ”
For i ＝ 1 To 3
For j ＝ 1 To 10 － i
If d(j) > d(j ＋ 1) Then
tt＝d(j)：d(j)＝d(j＋1)：d(j＋1)＝tt
End If
Next j
s ＝ s ＋ Str(d(i))
Next i
text1.Text ＝ s
数组元素d(1)到d(10)的值分别是91、28、83、62、64、36、9、65、37、99，经过该程序段“加工”后，文本框Text1中显示的内容为( )
A．9 28 37 B．99 91 83
C．28 9 36 D．28 62 36
解析 此算法属于从前往后冒泡排序算法，且只排了3趟。第1趟把91移动到后面，第2趟把83移动到后面。
答案 D
8．有如下VB程序段：
For i ＝ 1 To 6
j ＝ 7
Do While j > i
If a(j) > a(j － 1) Then
a(j)＝a(j)＋a(j－1)：a(j－1)＝a(j)－a(j－1)：a(j)＝a(j)－a(j－1)
End If
j ＝ j － 1
Loop
Next i
For i ＝ 3 To 6
s ＝ s ＋ a(i)
Next i
Label1.Caption ＝ Str(s)
已知数组元素a(1)到a(7)的值依次为“8，2，3，7，10，6，5”，则执行该程序段后，标签Label1中显示的是( )
A．21 B．26 C．41 D．18
解析 这三条语句a(j)＝a(j)＋a(j－1)：a(j－1)＝a(j)－a(j－1)：a(j)＝a(j)－a(j－1)的作用是交换a(j)和a(j－1)，因此是从后往前的冒泡升序算法。把5＋6＋7＋8输出。
答案 B
9．有如下VB程序段：
Dim a(5) As Integer, b(5) As Integer
a(1) ＝ 2: a(2) ＝ 5: a(3) ＝ 2: a(4) ＝ 5: a(5) ＝ 4
b(1) ＝ 14: b(2) ＝ 23: b(3) ＝ 32: b(4) ＝ 44: b(5) ＝ 56
For i ＝ 1 To 4
For j ＝ 5 To i ＋ 1 Step －1
If a(i) > a(j) Then
t ＝ a(i): a(i) ＝ a(j): a(j) ＝ t
t ＝ b(i): b(i) ＝ b(j): b(j) ＝ t
ElseIf a(i) ＝ a(j) And b(i) < b(j) Then
t ＝ b(i): b(i) ＝ b(j): b(j) ＝ t
End If
Next j
Next i
则运行该程序后，数组b中各元素的值依次是( )
A．32 14 56 44 23 B．14 32 56 23 44
C．14 23 32 44 56 D．56 44 32 23 14
解析 本题考核的知识点是冒泡排序的应用。本题中对a数组从小到大排列，同时如果a数组元素的值相等，且所对应的b数组前面的比后小，要交换b数组元素的值。
数组下标i
排序前
排序后
a(i)
b(i)
a(i)
b(i)
1
2
14
2
32
2
5
23
2
14
3
2
32
4
56
4
5
44
5
44
5
4
56
5
23
答案 A
10．实现某算法的部分VB 程序段如下：
i ＝ 1
Do While i <＝ 5
p ＝ 6
For j ＝ 6 To i ＋ 1 Step －1
If a(j) < a(j － 1) Then
t ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ t
p ＝ j
End If
Next j
i ＝ p
n ＝ n ＋ 1
Loop
Text1.Text ＝ Str(n)
数组元素 a(1)到a(6)的数据依次为“8，3，9，16，22，2”，则程序运行后，文本框Text1中显示的内容为( )
A．2 B．3 C．4 D．5
解析 变量n表示排序的趟数，第1趟排序结果2, 8, 3, 9，16，22，最后交换的元素为a(2)和a(1)，此时i＝2；第2趟排序结果2, 3，8, 9，16，22，最后交换的元素为a(3)和a(2)，此时i＝3；第3趟排序时，数据没有交换，因此i＝6，退出循环。
答案 B
11．某VB程序段如下：
i ＝ 1
Do While i <＝ 3
k ＝ i
j ＝ i ＋ 1
Do While j <＝ 5
If a(j) < a(k) Then k ＝ j
j ＝ j ＋ 1
Loop
If i <> k Then t ＝ a(i): a(i) ＝ a(k): a(k) ＝ t
i ＝ i ＋ 1
Loop
数组元素a(1)到a(5)的依次为“17，87，36，22，45”，则程序运行后，数组元素数据依次是( )
A．87，45，36，17，22 B．17，22，36，45，87
C．17，22，36，87，45 D．87，45，17，36，22
解析 这是选择排序，但只排了3趟。条件 a(j) < a(k)表示升序。
答案 C
12．有如下 VB 程序段：
For i ＝ 5 To 4 Step －1
k ＝ i
For j ＝ 6 － i To 1 Step －1
If a(j) < a(k) Then k ＝ j
Next j
If i <> k Then
t ＝ a(i): a(i) ＝ a(k): a(k) ＝ t
End If
Next i
数组元素 a(1)到 a(5)的值依次为“41，66，70，83，31”，经过该程序段“加工”后，数组元素a(1)到a(5)的值依次为( )
A．31，41，66，83，70 B．83，70，66，41，31
C．83，66，70，41，31 D．31，41，66，70，83
解析 该算法不是选择排序，只能采用分类讨论的思想进行解题。当i＝5时，For j＝1 To 1 Step－1没有交换。当i＝4时，For j＝2 To 1 Step－1 找到最小数是41。
答案 C
13．有如下VB程序段：
For i ＝ 1 To 5
For j ＝ i ＋ 1 To 6
If s(i) ＋ s(j) < s(j) ＋ s(i) Then
t ＝ s(j): s(j) ＝ s(i): s(i) ＝ t
End If
Next j
Next i
For i ＝ 1 To 6
Text1.Text ＝ Text1.Text ＋ s(i)
Next i
如果程序运行，一开始当数组元素s(1)到s(6)的值依次为“4”、“343”、“312”、“12”、“246”、“121”，运行该段代码后，文本框Text1中显示的内容为( )
A．434331224612121 B．434331224612112
C．343312246121124 D．121122463123434
解析 这是对字符串的操作，进行字符串的连接。当i＝1、2、3时，a(i)连接起来是较大值，没有交换。
答案 B
14．有如下VB程序段：
tail ＝ 6: i ＝ 1: r ＝ 2
Do While i < r
For j ＝ tail 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
i ＝ i ＋ 1
For j ＝ i To tail － 1
If a(j) < a(j ＋ 1) Then
t ＝ a(j): a(j) ＝ a(j ＋ 1): a(j ＋ 1) ＝ t
End If
Next j
tail ＝ tail － 1
Loop
数组元素值“73、56、28、61、44、92”，运行程序，数组元素a(1)到a(6)的值依次为( )
A．73，61，56，92，44，28 B．92，73，56，61，44，28
C．92，73，61，56，28，44 D．92，73，61，56，44，28
解析 这是进行首尾同时排序。
答案 D
15．完成某排序算法的VB程序段如下：
For i ＝ 1 To 7
k ＝ 0
For j ＝ 8 To i ＋ 1 Step －1
If a(j) Next j
If k ＝ 0 Then Exit For
Next i
如果用上述算法对数据序列：38，11，21，62，59，65，77，79进行排序(数据分别存储在数组元素 a(1)～a(8)中)，实现数据有序时所经历的排序遍数是( )
A．2 B．3 C．4 D．7
解析 采用从后往前冒泡排序算法。变量k表示每趟交换的次数，若某趟没有进行数据交换，表示数据已经有序，可以提前退出循环。第1趟的结果是11，38，21，59，62，65，77，79，第2趟的结果是11，21，38，59，62，65，77，79，在第2趟中还有数据交换，因此共排了3趟。
答案 B
16．有如下VB程序段：
n ＝ 8: flag ＝ True: k ＝ 0
First ＝ 1: Last ＝ n
Do While flag
p ＝ False: flag ＝ False
For j ＝ Last To First ＋ 1 Step －1
k ＝ k ＋ 1
If a(j) < a(j － 1) Then
t ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ t
First ＝ j: flag ＝ True
If p ＝ False Then Last ＝ j: p ＝ True
End If
Next j
If Last <> n Then Last ＝ Last ＋ 1
Loop
数组元素a(1)到a(8)值依次为“2，8，12，17，13，14，18，19”，程序运行后，变量k的值为( )
A．3 B．8 C．9 D．28
解析 本题主要考查排序算法的优化。flag表示是否有序的标志，First表示最后一次前面交换的位置，如果前面的有序，下次First的位置开始比较。Last表示后面第一次交换的位置，后面Last＋1至n肯定是有序的，只要跟Last＋1进行比较比较就可以了。变量k表示排序的趟数。
答案 A
17．有如下程序段：
For i ＝ 1 To 3
For j ＝ i ＋ 1 To 7
If a(j) < a(i) Then
k ＝ a(j): a(j) ＝ a(i): a(i) ＝ k
c ＝ c ＋ 1
End If
Next j
s ＝ Str(a(i)) ＋ s
Next i
Text1.Text ＝ Str(c) & “：” & s
数组元素a(1)至a(7)中值分别为3，9，1，5，8，6，2，该程序段运行后，文本框Text1中显示的内容是( )
A．5：6 8 9 B．3: 9 8 6 C．3：1 2 3 D．5：3 2 1
解析 比较对象为a(j)和a(i)，不是相邻元素，因此不属于冒泡算法，只能采用分类讨论的思想，其中变量c表示总的交换次数。当i＝1时，For j＝2 To 7。结果为1，9，3，5，8，6，2，交换1次；当i＝2时，For j＝3 To 7。结果为1，2，9，5，8，6，3，交换2次；当i＝3时，For j＝4 To 7。结果为1，2，3，9，8，6，5，交换2次；共交接了5次，把前面3个数进行反向连接。
答案 D
18．有如下VB程序段：
i ＝ 1
Do While i <＝ 6
t ＝ Int(Rnd * 10) ＋ 1
If t Mod 2 ＝ i Mod 2 Then a(i) ＝ t : i ＝ i ＋ 1
Loop
For i ＝ 1 To 2
k ＝ 1
For j ＝ 1 To 6 －i * 2
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
执行该程序段后，数组元素a(1)到a(6)的值可能是( )
A．5，9，2，10，7，8 B．9，0，7，2，3，4
C．9，2，5，4，3，8 D．1，8，7，6，9，4
解析 满足条件t Mod 2 ＝ i Mod 2表示奇数位是奇数，偶数位是偶数。a(j)和a(j＋2)比较和交接，表示是奇数位和偶数位分别排序，其中奇数位是升序，偶数为降序。
答案 D
二、非选择题
19．有一组正整数，要求仅对其中的奇数进行升序排序。排序后在列表框List2中也仅显示奇数部分数据，结果如图所示。
实现上述功能的VB代码如下，但加框处有错，请改正。
Const n ＝ 10
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim t As Integer, i As Integer, j As Integer, m As Integer
Dim tmp As Integer
′读取一组正整数，存储在数组a中，并显示在列表框List1，代码略
i ＝ 1
Do While i <＝ n
For j ＝ n To i ＋ 1 Step －1
If a(j) Mod 2 ＝ 1 Then
If Then′(1)
tmp ＝ a(j) : a(j) ＝ a(j － 1) : a(j － 1) ＝ tmp
t ＝ t ＋ 1
End If
End If
Next j
If Then m ＝ m ＋ 1 ′(2)
i ＝ i ＋ 1
Loop
For i ＝ 1 to m
List2.AddItem Str(a(i))
Next i
List2.AddItem ”一共交换了” & t & ”次”
End Sub
解析 这是典型的冒泡排序，但只要求对奇数进行排序，因此当奇数与偶数比较时，把偶数换到后面。M表示奇数的数量。
答案 (1)a(j) < a(j － 1) Or a(j － 1) Mod 2 ＝ 0 (2)a(i) Mod 2 ＝ 1
20．编写一个 VB 程序实现数据左右交替上升排序。功能如下：随机产生 n 个不重复的整数存数组 a，并在列表框 list1 中显示，单击“排序”按钮 Command1，在列表框list2 中显示排序后的数据。某遍程序运行后，数组 a 中存储的左右交替上升排序的 n 个正整数，如下表所示：
a(1)
a(2)
a(3)
……
a(n－2)
a(n－1)
a(n)
1
4
7
……
8
6
2
实现该功能的 VB 程序如下，但加框处代码有错，请改正。
Const n ＝ 10
Dim a(1 To n) As Integer
Private Sub Form_Load()
′随机产生n个不重复的整数存数组a，并在列表框List1中显示。代码略。
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer
Dim imin1 As Integer, imin2 As Integer
For i ＝ 1 To n '2
imin1 ＝ i
imin2 ＝ i ＋ 1
If a(imin1) > a(imin2) Then t ＝ imin1: imin1 ＝ imin2: imin2 ＝ t
For j ＝ i ＋ 2 To n － i ＋ 1
If a(j) < a(imin1) Then
imin2 ＝ imin1: imin1 ＝ j
′(1)
imin2 ＝ j
End If
Next j
If i <> imin1 Then t ＝ a(i): a(i) ＝ a(imin1): a(imin1) ＝ t
If imin2 ＝ i Then ′(2)
If n－i＋1<>imin2 Then
t＝a(n－i＋1)：a(n－i＋1)＝a(imin2)：a(imin2)＝t
End If
Next i
′在列表框List1中显示排序后的数组a。代码略。
End Sub
解析 变量imin2表示次大者，当把j赋值给imin2时，需满足imin2 > a(j)。位置n－i＋1是与i的对称位置。
答案 (1)ElseIf imin2 > a(j) Then (2)imin2 ＝ imin1
21．某会议室收到 10 场会议使用申请，会议室使用安排要求：①会议时间不冲突；②一天内安排的会议场数最多；③优先安排结束时间早的会议。小李编写了一个 VB 程序，在 List1 中显示按结束时间升序排序的 10 场会议，List2 中显示最终会议安排方案，运行界面如图所示。已知每场会议的开始、结束时间分别保存在数组 a 和数组 b 中，比如第 i 场会议，开始时间保存在 a(i)中，结束时间保存在 b(i)中。
实现上述功能的 VB 程序如下，但加框处代码有错，请改正。
Private Sub Command1_Click()
Dim a(1 To 20) As Single
Dim b(1 To 20) As Single
Dim i As Integer
Const kaishi ＝ 8 ′会议室开门时间
Const jieshu ＝ 17 ′会议室关门时间
′此处代码实现分别录入每场会议的开始、结束时间并存入相应数组， 代码略
For i ＝ 1 To 9
k ＝ i
For j ＝ i ＋ 1 To 10
If Then k ＝ j ′(1)
Next j
If k <> i Then
t ＝ a(i): a(i) ＝ a(k): a(k) ＝ t
t ＝ b(i): b(i) ＝ b(k): b(k) ＝ t
End If
Next i
For i ＝ 1 To 10
List1.AddItem a(i) & ”点” & ”－” & b(i) & ”点”
Next i
k ＝ 1
Do While a(k) < kaishi
k ＝ k ＋ 1
Loop
t ＝ b(k)
List2.AddItem a(k) & ”点” & ”－” & b(k) & ”点” ′输出第一场会议的时间
For i ＝ k ＋ 1 To 10
If b(i) <＝ jieshu Then
If a(i) >＝ t Then
List2.AddItem a(i) & ”点” & ”－” & b(i) & ”点”
′(2)
End If
End If
Next i
End Sub
解析 优先安排结束时间早的会议，因此是按结束时间进行升序排列。要求会议不能重叠，因此t表示下场会议的开始时间不能早于该时间，因此应记录为当场会议的结束时间。
答案 (1)b(k) > b(j) (2)t ＝ b(i)
22．小李基于选择排序算法编写了一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Const n ＝ 10
Private Sub Form_Load()
′排序前数据存储在数组a中，并在文本框Text1中显示．代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer，bottom As Integer
Dim a(1 To n) As Integer ，j As Integer
i ＝ 1：bottom ＝ n
Do While i < bottom
k ＝ i
j ＝ i ＋ 1
Do While j <＝ bottom
If a(j) ＝ a(k) Then
a(j) ＝ a(bottom)
′(1)
bottom ＝ bottom － 1
ElseIf a(j) < a(k) Then
k ＝ j
End If
j ＝ j ＋ 1
Loop
If Then ′(2)
t ＝ a(i): a(i) ＝ a(k): a(k) ＝ t
End If
i ＝ i ＋ 1
Loop
′排序后数据存储在数组a中，并在文本框Text2中显示
End Sub
解析 当两个数相等时，用后面的数替换当前相等的数，同时还要跟j位置是的数再次进行比较。
答案 (1)j＝j－1 (2)k<>i
23．小李编写“合并区间”VB 程序，功能如下：窗体加载时，获取并存储合并前的区间数据，并显示在列表框 List1 中。单击“合并”按钮后，以区间左端点数值对区间进行升序排序，然后相邻区间的相交进行合并，最后在列表框 List2 上显示合并后的区间。程序运行如图所示：
实现上述功能的 VB 程序如下，在划处填入合适的代码。
Dim a(1 To 20) As Integer ′存储区间的左端点数值
Dim b(1 To 20) As Integer ′存储区间的右端点数值
Private Sub Form_Load()
′将区间左端点存入 a，区间右端点存如数组 b，并在列表框 List1 显示，代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim curL As Integer, curR As Integer
For i ＝ 1 To n － 1
For j ＝ 1 To__①__
If __②____Then
t ＝ a(j): a(j) ＝ a(j ＋ 1): a(j ＋ 1) ＝ t
t ＝ b(j): b(j) ＝ b(j ＋ 1): b(j ＋ 1) ＝ t
End If
Next j
Next i
curL ＝ a(1): curR ＝ b(1)
For i ＝ 2 To n
If a(i) <＝ curR Then
If curR < b(i) Then __③__
Else
List2.AddItem ”[” ＋ Str(curL) ＋ ”，” ＋ Str(curR) ＋ ”]”
curL ＝ a(i): curR ＝ b(i)
End If
Next i
List2.AddItem ”[” ＋ Str(curL) ＋ ”，” ＋ Str(curR) ＋ ”]”
End Sub
解析 运用的是从前往后的冒泡排序算法，按存储区间的左端点数值，比较的对象是a(j)和a(j＋1)，当a＋1达到i的对称位置n－i＋1时，此时j为n－i。条件a(i) <＝ curR成立时，说明当前区间和上一区间有重合，当curR < b(i)条件成立时，右区间为b(i)。
答案 ①n－i ②a(j)>a(j ＋ 1) ③curR＝b(i)
课件67张PPT。专题七 排序算法的程序实现【考纲标准】1．(2018·4月浙江选考)有一组正整数，要求仅对其中的素数进行升序排序。排序后素数在前，非素数在后。排序示例如下。实现上述功能的VB程序如下，但加框处代码有误，请改正。
Const n ＝ 8
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, t As Integer
Dim flag As Boolean
′读取一组正整数，存储在数组a中，代码略
For i ＝ 1 To n － 1 End If
End If
Next j
If k <> i Then
t ＝ a(k): a(k) ＝ a(i): a(i) ＝ t
End If
If Not flag Then Exit For ′Exit For表示退出循环
Next i
′依次输出排序后的数据。代码略
End Sub
Function IsPrime(m As Integer) As Boolean ′本函数判断m是否是素数：是素数返回值为True，不是素数返回值为False
′代码略
End Function
解析 交换两个数的语句出现在外循环中，说明是选择排序，变量k表示每趟排序中的最值，因此k的初值是i。题目是要求仅对其中的素数进行升序排序，因此比较的对象a(k)还要求是素数。
答案 (1)k＝i
(2)Not flag Or a(j) 或Not IsPrime(a(k)) Or a(j) 或Not flag Or flag And a(j) 或Not IsPrime(a(k)) Or IsPrime(a(k)) And a(j) Const n＝10
Dim a(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer，j As Integer，t As Integer
Dim bottom As Integer ′剔除重复数据后元素的个数解析 本题考核从后往前冒泡的算法思想。从后往前冒泡，前面的数据先有序，当两次比较的数据a(j－1)和a(j)中相等时，a(j－1)可能已经有序，因此用最后一个数据替换a(j)，同时数据的有效长度bottom少1个。
答案 (1)a(j)a(j) 或其他等价表达式
(2)a(j)＝a(bottom) 或其他等价语句3．(2016·10月浙江省技术选考)小吴为了研究冒泡排序过程中数据的“移动”情况，编写了一个VB程序，功能如下：在列表框List1中显示排序前数据(存储在数组a中)，在文本框Text1中输入初始位置(即下标值)，单击“排序”按钮Command1后，在标签Label1中显示指定初始位置的数据在排序过程中的位置变化情况，排序后的数据显示在列表框List2中。程序运行界面如图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。
Dim a(1 To 8) As Integer
Dim n As Integer
Private Sub Form_Load()a(1)＝30：a(2)＝47：a(3)＝30：a(4)＝72
a(5)＝70：a(6)＝23：a(7)＝99：a(8)＝24
n ＝ 8For i ＝ 1 To 8
List1.AddItem a(i)
Next i
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer
Dim pos As Integer
Dim s As StringEnd If
End If
Next j
Next i
Label1.Caption ＝ “位置变化情况：” ＋ s
For i ＝ 1 To n
List2.AddItem Str(a(i))
Next i
End Sub解析 第一处改错实现的是两个变量的交换。交换变量a(j)和a(j－1)的值后，该两个元素数据位置发生变化，接下来判断这两个元素的下标是否和pos相同，如果pos和j相同，已经被交换到j－1位置，pos需要更新，否则如果pos和j－1相同，已经被交换到j位置，pos需要更新。
答案 (1)k ＝ a(j－1) (2)ElseIf pos ＝ j － 1 Then1．排序的作用是把n个数据从小到大或从大到小重新排列，使得a(1)至a(n)中的数据有序。排序的方法有很多，重点掌握冒泡排序和选择排序。
2．n个数据一般需要经过n－1趟排序，变量i控制排序的趟数。第i趟的比较次数往往有n－i次。
3．变量j表示比较大小的元素位置，其中数组元素a(j－1)表示第j－1个位置的数组元素，他位于a(j)的前面第一个元素，a(j＋1)位于a(j)的后面第一个元素。
4．内部循环(j的循环)初值和终值决定了排序的区间和方向。如果初值大于终值，初值往往是n，表示从后往前向后排序，若j的初值小于终值，初值往往是1，表示从前往后排序。考点1 从后往前冒泡排序
1．以n(n＝5)个元素从后往前冒泡升序排序为例，完成下列表格。 ①第i趟冒泡，把最大或最小的元素交换到第i位置，实现从第1个位置到第i个位置的元素有序。数组前面的元素先有序。
②第i趟排序的区间是[i，n]，因此每趟排序的比较的位置(j的初值)为n。2．每趟排序的算法
第i趟的排序实现在区间[i，n]中，从第n个位置的数开始，依次与前面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j－1)，比较完后向前移动，直到j－1的位置到达最前面的位置i为止，此时j＝i＋1。实现区间[1，i]的数据有序。3．若每趟交换的次数为0，表示所有数据均有序，可以提前结束排序算法。也可以记flag的状态为False，若发生交换，将flag的值修改为True，根据flag的值，也可以表示数据是否有序。
4．每趟排序实现了[1，i]之间的数据有序，因此下趟排序的区间为[i＋1，n]。记录第i趟排序最后一次交换的位置j，此时表示[1，j－1]已经有序，下趟排序的区间可以修改为[j，n]，当j大于i＋1时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。5．核心代码【例1】 小刘在研究n个数的冒泡排序算法时，发现可以从两个方面进行优化：
(1)在每遍冒泡过程中，若最后一次交换的是last与last－1位置的数，则last－1位置之前的相邻数据均已有序。进行下一遍冒泡时，无序区域设置为[last，n]。
(2)若在某一遍排序中没有数据交换，说明待排序数据都已经有序，冒泡排序过程可在此遍排序后终止。
小刘按上述方法编写的冒泡优化VB程序，功能如下：程序运行时生成100个随机整数存入数组a，并显示在列表框List1中。单击“排序”按钮Command1后，对数组a中的数据进行排序，排序后的数据显示在列表框List2中，排序过程中实际的冒泡遍数显示在标签Label3上。程序运行界面如图所示。实现上述功能的VB程序如下，但加框处代码有错，请改正。
Dim a(1 To 100) As Integer
Private Sub Form_Load()
′产生100个无重复的三随机整数，存入数组a并显示在列表框list1中
′代码略 If a(j) > a(j － 1) Then
t ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ t
last ＝ j－1
flag ＝ True ′有交换发生
End If
Next j
n ＝ n ＋ 1
Loop
For i ＝ 1 To 100 List2.AddItem Str(a(i))
Next i
Label3.Caption ＝ “本次排序的冒泡遍数为：” & Str(n)
End Sub
其中，方框(1)处应改正为________；
方框(2)处应改正为________。解析 flag表示有无交换的标志，如果本趟中没有发生数据的交换，表示数据已经有序，flag ＝ True语句出现在交换模块中，有交换还要循环，因此循环的条件是flag ＝ True。每趟比较的结束位置是last ＋ 1，但从大到小的步长是－1。
答案 (1)flag (2)j＝100 to last－1 Step －1【例2】 有如下程序段：For i ＝ 1 To 5
For j ＝ 10 To i ＋ 2 Step －1
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)至a(10)的值分别为“3，17，2，14，15，6，7，18，9，4”，执行该程序段后，数组元素a(8)中的值为( )
A．3 B．4 C．15 D．17
解析 从比较对象a(j)和a(j－2)看，属于奇数位和偶数位分别进行升序排列，每趟有2个数据有序，因此只要进行n2趟排序。偶数位的数据有17,14,6,18,4，升序排列中第2大的数是17。
答案 D【变式训练1】 有一组正整数，基于冒泡排序对其中的数进行升序排序。排序后奇数在前，偶数在后。排序示例如下实现上述功能的VB程序如下，但加框处代码有误，请改正。
Const n ＝ 10
Dim d(1 To n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer t ＝ d(j): d(j) ＝ d(j － 1): d(j － 1) ＝ t
End If
Next j
i ＝ i ＋ 1
Loop
′依次输出排序后的数据，代码略
End Sub
解析 条件d(j) Mod 2 ＝ d(j － 1) Mod 2成立，表示相邻两个数都是奇数或都是偶数，相邻两个数进行比较，并且把小的数换到前面。如果是一奇一偶，且偶数在前，要把偶数换到后面。
答案 (1)a(j)1．对称位置：在数组a(1)至a(n)中，有下列数组元素的位置是左右对称的，如a(1)与a(n)，a(2)与a(n－1)，a(3)与a(n－2)等，两个左右对称数组元素位置的下标之和是一个定值n＋1，因此可以到结论：与下标为i的数组元素左右对称的位置是n－i＋1。2．以n(n＝5)个元素从前往后冒泡升序排序为例，完成下列表格。 ①第i趟冒泡，把最大或最小的元素交换到与他左右对称的位置n－i＋1的位置，实现从第n－i＋1个位置到第n个位置的元素有序。数组后面的元素先有序。
②第i趟排序的区间是[1，n－i＋1]，因此每趟排序的比较的位置(j的初值)为1。
3．每趟排序的算法
第i趟的排序实现在区间[1，n－i＋1]中，从第1个位置的数开始，依次与后面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和a(j＋1)，比较完后向后移动，直到j＋1的位置到达最后面的位置n－i＋1为止，此时j＝ n－i。实现区间[n－i＋1，n]的数据有序。4．每趟排序实现了[n－i＋1，n]之间的数据有序，因此下趟排序的区间为[1，n－i]。记录第i趟排序最后一次交换的位置j，此时表示[j＋1，n]已经有序，下趟排序的区间可以修改为[1，j]，当j小于n－i时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。5．核心代码【例3】 小李基于冒泡排序算法编写一个VB程序，功能如下：在文本框Text1中显示排序前的数据，单击“排序”按钮Command1，在文本框Text2中显示剔除重复数据后的升序排序结果。程序运行界面如下图所示。实现上述功能的VB程序如下，请将划线处填写完整。
Const n ＝ 10
Dim a(n) As IntegerPrivate Sub Form_Load()
′产生n个随机数，并显示在文本框Text1中，代码略End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer
Dim top As Integer, s As String
top ＝ 1: i ＝ 1
Do While i <＝ n － 1
____①____Do While j <＝ n － i
If a(j) > a(j ＋ 1) Then
t ＝ a(j): a(j) ＝ a(j ＋ 1): a(j ＋ 1) ＝ t
ElseIf a(j) ＝ a(j ＋ 1) Then
____②____
top ＝ top ＋ 1
End If
j ＝ j ＋ 1
Loop i ＝ i ＋ 1
Loop
s ＝ " "
For i ＝ top To n
s ＝ s ＋ Str(a(i))
Next i
Text2.Text ＝ s
End Sub解析 从语句Do While j <＝ n－i来看，属于从前往后冒泡，比较的对象是a(j)和a(j＋1)，因此数据从后面开始有序，当两个数据是重复时，把开头的数据替换a(j)，继续排序，变量top表示不重复数据的开始位置，j的初值从top开始。
答案 ①j ＝ top ②a(j) ＝ a(top)【变式训练2】 小赵对冒泡升序排列算法进行了如下改进：在一趟排序中，同时进行从最后一个元素向前的比较并交换和从第一个元素向后比较并交换，把最小的元素交接到前面，把最大的元素交换到后面，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序如下，但加框处代码有错，请改正。
Dim a(8) As Integer, i As Integer
Const n ＝ 8
Private Sub Command1_Click()Loop
For i ＝ 1 To n
List2.AddItem Str(a(i))
Next i
End Sub
Private Sub Form_Load()
′产生8个随机数，并显示在列表框List1中，代码略
End Sub解析 先用从后往前的冒泡排序，将小的数排到前面，再用从前往后冒泡排序的方法，把较大的数排序后面，直到所有数据有序。
答案 (1)last To start ＋ 1 Step －1 (2)last ＝ last － 1 考点3 选择排序
一、排序思想
在数据区间[i，n]范围内，查找最值的位置k，并把该位置的数与第i个数进行交换，使得[1，i]数据有序，重复执行n－1趟。该算法包括两个步骤，一是查找区间[i，n]中最值位置k，二是交换位置k与位置i上值。二、算法实现
1．理解变量i、j和k的含义
变量i控制排序的趟数，n个数需要通过n－1趟(轮)排序；变量j表示比较大小的元素位置，k表示每趟中最大或最小数所在位置。
2．比较的方向和步骤
第i趟排序：在区间[i，n]中查找最值的位置k。每趟k的初值默认在第i个位置，因此比较的范围在[i＋1，n]，每次比较的位置j在最值k的后面。3．以5个元素a(1)至a(5)选择排序升序为例。①表示可以看出，第i趟排序的区间是[i，n]，因此比较位置j每次从i＋1开始，一直到最后，用最值k所在位置的数a(k)与a(j)，如果a(k)②在比较过程中，只是发生了k值的更新，而没有进行数据交换，即每趟最多只交换了一次。
③每趟数据是否交换的条件取决于k值是否发生了更新。4．冒泡排序与选择排序的区别For i＝1 To n－1 ′n个数共进行n－1趟排序
K＝i ′第i趟排序时，首先用k记录i
For j＝i＋1 To n ′k位置上的数依次与j位置上的数进行比较
If a(j) Next j
If k<>i Then ′若i位置上的数不是最小数，则和k位置上的数进行互换
temp＝a(i)：a(i)＝a(k)：a(k)＝temp
End If
Next i【例4】 小赵对选择排序算法进行了如下改进：在数组的所有元素中找出最小和最大数据的元素，然后将这两个元素分别与第一个和最后一个元素交换数据，在余下的元素中找出最小和最大数据的元素，分别与第二个和倒数第二个元素交换数据，以此类推，直到所有元素的数据按升序排列。小赵编写的VB程序段如下：
p＝1：q＝10
Do While p < q要使程序实现上述算法思想，则方框中的语句是( )
A．If iMax＝ p Then iMax ＝ iMin
B．If iMin＝ p Then iMin ＝ iMax
C．If iMax＝ p Then iMin ＝ iMax
D．If iMin＝ p Then iMax ＝ iMin解析 该算法是对选择排序算法的改进，由原来的找到最大数(或最小数)后从一个方向排序改为从最小和最大两个方向同时进行排序；每趟排序a(iMin)为找到的最小数，a(iMax) 为找到的最大数；最小数a(iMin)和a(p)交换，排到前边，然后最大数a(iMax)和a(q)交换，排到后边，实现升序排列；在每一趟循环中，如果没有方框中的语句，在a(p)恰好为最大数a(iMax)(即imax＝p)时，因为最小数a(iMin)和a(p)先进行交换，交换后a(iMax)会变成最小数，a(iMax)和a(q)再进行交换会把最小数交换到a(q)而出现错误；方框中的语句应为避免这一错误的语句，A正确。分析程序时可以从待选项中获取线索。
答案 A【变式训练3】 从数据库中读取各考生的编号、笔试和面试成绩，在文本框Text1中输入录取人数，按笔试与面试成绩之和从高到低录取，若成绩之和相等，面试成绩高的排前面。当录取人数达到计划录取人数时，若有面试加笔试的总分与之相等的分数，也要作为录取对象。程序运行的界面如图所示：VB程序代码如下，但加框处的代码有错，请改正。
Const n ＝ 266
Dim ms(n) As Integer, bs(n) As Integer, bh(n) As Integer
Private Sub Command1_Click()
Dim i As Integer, j As Integer, k As Integer, s As String
For i ＝ 1 To n － 1
k ＝ i
For j ＝ i ＋ 1 To nIf ms(j) ＋ bs(j) > ms(k) ＋ bs(k) Then
k ＝ j If ms(j) > ms(k) Then k ＝ j
End If
Next j
If k <> i Then
t ＝ ms(k): ms(k) ＝ ms(i): ms(i) ＝ t
t ＝ bs(k): bs(k) ＝ bs(i): bs(i) ＝ t
t ＝ bh(k): bh(k) ＝ bh(i): bh(i) ＝ t s ＝ s ＋ Str(bs(i)) ＋ "＋ " ＋ Str(ms(i)) ＋ " ＝ " ＋ Str(bs(i) ＋ ms(i))
List1.AddItem s
i ＝ i ＋ 1
Loop
End Sub
Private Sub Form_Load()
′从数据库中读取各考生的编号(bh数组)、笔试(bs数组)和面试(ms数组)成绩，分别存储在相应的数组中
End Sub解析 第一部分为选择排序，有两种情况要交换，即总分大于前者，或者总分相等，但笔试高的，因此为多分支选择结构。第二部分为输出，输出的条件有两个，即输出的人数比计划录取人数少；或者已经达到计划录取人数，却还存在总分与计划录取最后一人的总分相等，也要输出。
答案 (1)ElseIf ms(j) ＋ bs(j) ＝ ms(k) ＋ bs(k)
(2)ms(i) ＋ bs(i) ＝ ms(i－1) ＋ bs(i －1)