专题21 冒泡排序 课件-2022届高三信息技术选考总复习（78张PPT）

(共78张PPT)
专题21 冒泡排序
一、什么是排序
排序的作用是把n个数据从小到大或从大到小重新排列，使得a(1)至a(n)中的数据有序。排序的方法有很多，重点掌握冒泡排序和选择排序。
1.n个数据一般需要经过______趟排序，变量i控制排序的趟数。第i趟排序时，前面i－1个数据已经有序，因此比较次数往往有n－(i－1)－1次，即______次。
2.变量j表示比较大小的元素位置，其中数组元素________表示第j－1个位置的数组元素，他位于a(j)的前面第一个元素，________位于a(j)的后面第一个元素。
n－1
n－i
a(j－1)
a(j＋1)
3.内部循环(j的循环)初值和终值决定了排序的区间和______。如果初值大于终值，初值往往是____，表示从____往____向后排序，若j的初值小于终值，初值往往是____，表示从____往____排序。第i趟排序中，待排序的数据个数有n－i＋1个，排序的次数即循环变量j的初值与终值差的绝对值为n－i。
4.冒泡排序是相邻两个元素进行比较，在判断是升序还是降序时，可以转换为前后两个元素的比较，如a(j)>a(j－1)表示他比他前面的数大，进行交换，因此是降序。如a(j)>a(j＋1)表示他比他后面的数大，进行交换，因此是升序。
方向
n
后
前
1
前
后
二、从后往前冒泡排序
(1)以n(n＝5)个元素从后往前冒泡升序排序为例，完成下列表格。
趟数 排序 区间 第1次 第2次 第3次 第4次 j终值 比较 次数 有序
区间
j j－1 j j－1 j j－1 j j－1 i＝1 ______ 5 4 4 3 3 2 2 1 2 4 ______
i＝2 ______ 5 4 4 3 3 2 3 3 ______
i＝3 ______ 5 4 4 3 4 2 ______
i＝4 ______ 5 4 5 1 ______
[1，n]
[1，1]
[2，n]
[1，2]
[3，n]
[1，3]
[4，n]
[1，4]
①第i趟冒泡，把最大或最小的元素交换到第i位置，实现从第1个位置到第i个位置的元素有序。数组前面的元素先有序。
②第i趟排序的区间是[i，n]，因此每趟排序的比较的位置(j的初值)为n。
(2)每趟排序的算法
第i趟的排序实现在区间[____，____]中，从第____个位置的数开始，依次与____面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和_________，比较完后向前移动，直到j－1的位置到达最前面的位置i为止，此时j＝________。实现区间[1，i]的数据有序。
i
n
n
前
a(j－1)
i＋1
三、从前往后冒泡排序
(1)对称位置：在数组a(1)至a(n)中，有下列数组元素的位置是左右对称的，如a(1)与a(n)，a(2)与a(n－1)，a(3)与a(n－2)等，两个左右对称数组元素位置的下标之和是一个定值n＋1，因此可以得到结论：与下标为i的数组元素左右对称的位置是_________。
(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 2 2 3 3 4 3 3 [_______]
i＝3 [________] 1 2 2 3 2 2 [_______]
i＝4 [________] 1 2 1 1 [_______]
n－i＋1
1，n－1
n－1，n
1，n－2
n－2，n
1，n－3
n－3，n
①第i趟冒泡，把最大或最小的元素交换到与他左右对称的位置_______的位置，实现从第n－i＋1个位置到第n个位置的元素有序。数组后面的元素先有序。
②第i趟排序的区间是[1，________]，因此每趟排序的比较的位置(j的初值)为1。
(3)每趟排序的算法
第i趟的排序实现在区间[____，_________]中，从第1个位置的数开始，依次与后面相邻的数比较，如果逆序即交换，比较和交换的对象为a(j)和__________，比较完后向后移动，直到j＋1的位置到达最后面的位置n－i＋1为止，此时j＝________。实现区间[n－i＋1，n]的数据有序。
n－i＋1
n－i＋1
1
n－i＋1
a(j＋1)
n－i
D
考点一　冒泡排序的算法思想
冒泡排序的特征是相邻的两个元素进行比较和交换，但比较的方向可以是从前面往后面，也可以是从后面往前面。要熟练掌握每趟排序比较次数、交换次数、有序的位置、待排序的区间和排序的结果。
【例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
解析　冒泡的方向可以从前往后排序，后面的数据先有序；也可以从后往前排序，前面的数据先有序。第一遍排序后的结果把最小的数排到了最前面，因此可以推断是升序排列。
B
【变式1】 对5个字母“5，9，6，3，8”进行两遍冒泡排序后即为某密码锁的密码，则下列字符串中可能为该密码的是(　　)
①35698　②98635　③35968　④96853
A.①② B.①④ C.②③ D.③④
解析　题目没有明确说是按降序还是升序排序，没有说明排序方向，所以有4种可能的情况。若对“5、9、6、3、8”进行两遍向后往前降序冒泡升序排列，其结果为将最小的两个数前移至第一第二的位置，则①符合题意；若对“5、9、6、3、8”进行两遍从前往后冒泡降序排列，则④符合题意。
D
【例2】 (2020·7月浙江选考)有如下 VB 程序段：
′生成6个随机正整数，依次存入数组元素 a(1)到 a(6)，代码略
For i＝1 To 2
For j＝6 To i＋1 Step －1
If a(j) Mod 3>a(j－1) Mod 3 Then
　　　　t＝a(j): a(j)＝a(j－1): a(j－1)＝t
End If
Next j
Next i
执行上述程序段后，下列选项中，a(1)到 a(6)各元素值不可能的是(　　)
A.2，1，4，3，6，7 B.5，2，1，7，8，3
C.7，7，6，3，3，1 D.8，7，4，3，3，2
解析　本题考查冒泡排序算法及其变形。各选项被 3 取余之后的结果如下：A.2，1，1，1，0，1　B.2，2，1，1，2，0　C.1，1，0，0，0，1　D.2，1，1，0，0，2。通过两趟冒泡排序肯定可以将数组中的最大前 2 项(取余后最大值)交换到 a(1)和 a(2)中，D 选项最大值2 还在最末位，显然不符合。
【变式2】 有如下VB程序段：
m＝Int(Rnd*4＋2)
For i＝1 To 6－m
For j＝1 To 6－i
If a(j)－a(j＋1)<0 Then
　　　　　　t＝a(j): a(j)＝a(j＋1): a(j＋1)＝t
End If
Next j
Next i
D
数组元素a(1)到a(6)的值依次为“49，45，5，61，42，71”，执行该程序段后，a(1)～a(6)各元素值不可能的是(　　)
A.61，49，71，45，42，5 B.49，45，61，42，71，5
C.49，61，45，71，42，5 D.71，61，49，45，42，5
解析　m的值可能是2，3，4，5，那么6－m的值可能是4，3，2，1。从比较和交换的对象以及内循环j从1到6－i来看，可以确定是从前往后冒泡降序排列，且只进行1－4趟的排序，分别列出每趟排序的结果。
【变式3】 有如下VB程序段：
a(1)＝6: a(2)＝9: a(3)＝3: a(4)＝7: a(5)＝8: a(6)＝1
t＝2*Int(Rnd*3)＋1
For i＝1 To 6－t
　For j＝6　To i＋1 Step －1
If a(j)　Next j
Next i
执行该程序段后，a(1)～a(6)各元素的值不可能是(　　)
A.1，6，9，3，7，8 B.1，3，6，9，7，8
C.1，3，6，7，9，8 D.1，3，6，7，8，9
解析　t的值可能是1，3，5，而6－t的值也是1，3，5，程序实现的功能是从后往前升序冒泡排列，分别列出1，3，5趟排列的结果。B选项是经过两趟排序的结果。
B
考点二　冒泡排序的算法实现
外层循环用来控制排序趟次(或待排序区间左边界)，内层循环用来扫描待排序区间，如果从后往前扫描，则前面的数先有序，左边界减少1个；如果从前往后扫描，则后面的数先有序，右边界减少1个。
关注点：
1.内层扫描的方向：向左还是向右？
2.哪个边界在移动？谁表示该边界？
3.防止数组越界：a(j＋1)还是a(j－1)？先代入特殊值，分析第1趟，第2趟中待排序区间左右边界的表示方法，再推广到一般情形。
D
【例3】 下列VB程序段的功能为：对数组a中的n个数据进行升序排序。
　　　 If a(j)　　　　　t＝a(j)∶a(j)＝a(j－1)∶a(j－1)＝t
End If
　 Next j
Next i
为实现上述功能，程序加框处的代码可以是(　　)
①n－i To 1 Step －1　②n To i＋1 Step －1　③1 To n－i　④2 To n－i＋1
A.①或③ B.①或④ C.②或③ D.②或④
解析　冒泡排序，比较交换相邻元素a(j)和a(j－1)，从前往后大的元素往后交换实现升序排序，此时内层循环变量j的取值范围是2到n－i＋1，也可以从后往前小的元素往前交换实现升序排序，此时内层循环变量j的取值范围是n到i＋1。故选项②④正确。
【变式4】 (2020·4月之江教育)某冒泡排序算法的VB程序段如下：
i＝6: flag＝1: cnt＝0
Do While i>＝2 And flag＝1
flag＝0: cnt＝cnt＋1
For j＝____________
If a(j)>a(j－1) Then
　　　　k＝a(j): a(j)＝a(j－1): a(j－1)＝k
　　　　flag＝1
End If
Next j
i＝i－1
Loop
B
数组元素a(1)到a(6)的值依次为“79，13，93，55，29，17”，执行该程序段后，cnt的值为3，数组元素实现有序，则方框中的代码是(　　)
A.2 To i－1 B.2 To i
C.6 To 7－i Step －1 D.6 To 8－ i Step －1
解析　从表达式a(j)>a(j－1)来判断，该程序实现降序排列，从后往前，需要排4趟，第5趟没有交换，因此cnt＝5，终点边界是i的对称位置(6－i＋1)，因此循环为6 To (6－i＋1)＋1 Step －1。从前往后，两趟有交换，第3趟没有交换，需要排每趟排序的区间和i有关系，i从大到小变化，表示右边界的值，因此扫描的方向从左往右，又因为比较的对象是a(j)和a(j－1)，因此j的初值只能为2，终值为右边界。
【变式5】 (2020·9月Z20)某冒泡排序算法的VB程序段如下：
i＝n
Do While i>＝2
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
i＝i－1
Loop
D
执行完上述程序段后，实现a数组元素有序排列，则划线处的代码可以是(　　)
①n To n＋2－i Step －1　②n To i＋1 Step －1　③2 To i　④2 To n－i
A.②③ B.②④ C.①④ D.①③
解析　比较的对象为a(j)和a(j－1)，若从后往前冒泡，由于i从n循环到2，因此每趟实现第n－i＋1个数据有序，排序的区间为[n－i＋1，n]，j的初值为n，终值为j－1等于n－i＋1时，内循环的最后一次是n－i＋2与n－i＋1比较。若从前往后冒泡，由于i从n循环到2，因此每趟实现第i个数据有序，排序的区间为[1，i]，j的初值为2，终值为j等于i时，内循环的最后一次是i与i－1比较。
【变式6】 (2020·7月浙江省选考)某校为学生期末考试分配考场，并编制准考证号。每个班级有班号，每位学生有班内序号，班内序号是按班级现有人数从1开始逐个编排的。准考证号格式为“入学年份＋班号＋班内序号”。每个考场有30个座位，座位号从1开始。连续分配座位的两个学生不属于同一个班级。
分配方法是：按考场号递增、同一考场座位号递增的顺序逐一分配座位。每次分配，先选班级，再选学生。选择班级时，在班级降序序列(按未分配人数)中选择第1个班级，但如果该班和前一次分配选定的班级相同，则改选第2个班级。选定班级后，再为该班未分配学生中序号最大的学生分配考场座位，并维护班级降序序列(按未分配人数)。
编写VB程序，实现考场分配功能：在文本框Text1中填写入学年份，单击“读取”按钮Command1后，将各班数据按人数降序显示在列表框List1中，然后单击“分配”按钮Command2，在列表框List2中显示分配结果。程序运行界面如图所示。
请回答下列问题：
(1)下列对象中，有Caption属性的是________(单选，填字母：A.Command1/B.Text1/C.List1)。
(2)实现考场分配功能的VB程序如下，请在划线处填入合适的代码。
(3)程序中加框处代码有错，请改正。
Dim n As Integer，y As String
Dim cla(1 To 20) As Integer，num(i To 20) As Integer
Dim room As Integer ′存储考场号
Dim seat As Integer ′存储座位号
Function fm(k As Integer) As String
′返回整数k(1≤k≤99)对应的数字字符串，不足两位左侧补”0”，代码略
End Function
Private Sub Command1_Click()
′从Text1中读取入学年份存入变量y，从数据库中读取该入学年份的班级数据，
′将班级个数存入变量n(1′各班班号均大于0，各班人数均未超过总人数的一半，
′将数组cla和num按班级人数降序排列后，显示在List1中，代码略
End Sub
Private Sub Command2_Click()
Dim i As Integer，t As Integer，s As Integer
Dim choice As Integer，m As Integer，f As Boolean
room＝1: seat＝1: choice＝0
____①____
Do While f＝True
If cla(1) <>choice Then m＝1 Else m＝2
choice＝cla(m)
′在列表框 List2 中显示准考证号、考场号、座位号
List2.AddItem y＋fm(cla(m))＋fm(num(m))＋” ”＋fm(room)＋” ”＋fm(seat)
seat＝seat＋1
If seat>30 Then
seat＝1
End If
num(m)＝num(m)－1
For i＝____②____ To n－1
If num(i)　　　　t＝num(i): num(i)＝num(i＋1): num(i＋1)＝t
　　　　s＝cla(i): cla(i)＝cla(i＋1): cla(i＋1)＝s
Else
　　　　Exit For ′Exit For 表示退出循环
End If
Next i
If____③____ Then f＝False
Loop
End Sub
答案　(1)A　(2)①f＝True　②m　③num(1)＝0　(3)room＝room＋1
解析　按钮对象Command1中有Caption属性。联系下文关系表达式 Do While f＝True 得知，变量 f 必须赋值为True，否则 f 的初值为 False，不能进入循环。当seat>30 意味着当前考场已经排满，需要增加一个新考场，而变量room 表示考场号，所以考场号递增 1，即 room＝room＋1。对每个班级剩下人数重新进行降序排序。因为一次外循环只安排一位考生，也就是cla(m)的班级人数减少1个，其他班级人数都不变只需从第m个位置开始往后冒泡即可。因为每次都会对班级剩下人数重新进行降序排序， 也就是说num(1)始终存储剩余班级中的最大人数。当 num(1)＝0 时就意味着所有班级完成考场分配。
【例4】 (2020·10月浙南名校)有如下VB程序段：
′生成6个随机正整数，依次存入数组a(1)到(6)，代码略
Const n＝6
k＝Int(Rnd*3)
For i＝1 To 2
For j＝1 To n－i－k
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(6)各元素的值不可能是(　　)
A.2，1，4，5，5，8 B.5，6，7，7，9，1
C.1，7，6，7，6，5 D.8，5，1，2，8，8
解析　此程序为冒泡排序，对[1，n－1－k＋1]范围内的值进行两趟从前往后的排序，且进行升序排列，k的取值范围为{0，1，2}，当k＝0时，排序范围为[1，n]，即对所有数进行两趟排序，可得到最后两位必然大于等于前面每一个数，即选项A、D都是可能的，当k＝1时，排序范围为[1，n－1]，即最后一位不参与排序，第n－1位与n－2位大于等于前面每一个数，B项是可能的，当k＝3时同理，故只有C不可能出现。
C
【变式7】 (2019·12月新力量)有如下程序段：
For i＝2 To 3
For j＝10 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
A
数组元素a(1)到a(10)的值依次为“66，34，12，59，21，26，18，45，20，16”，经过该程序段“加工”后，数组元素a(1)到a(10)的值依次为(　　)
A.66，12，16，34，18，59，21，26，20，45
B.12，16，18，20，21，26，34，45，59，66
C.66，59，45，34，12，26，21，20，18，16
D.12，16，18，66，34，20，59，21，26，45
解析　本题主要考查冒泡排序。i＝2时，从后往前，对a(10)－a(2)范围进行相邻数比较，升序排列，i＝3时，从后往前，对a(10)－a(3)范围进行相邻数比较，升序排列，需注意a(1)不参加排序。
考点三　冒泡的优化
1.若每趟交换的次数为0，表示所有数据均有序，可以提前结束排序算法。也可以记flag的状态为False，若发生交换，将flag的值修改为True，根据flag的值，也可以表示数据是否有序。
2.从后往前冒泡的每趟排序实现了[1，i]之间的数据有序，因此下趟排序的区间为[i＋1，n]。记录第i趟排序最后一次交换的位置j，此时表示[1，j－1]已经有序，下趟排序的区间可以修改为[j，n]，当j大于i＋1时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。
3.从前往后冒泡的每趟排序实现了[n－i＋1，n]之间的数据有序，因此下趟排序的区间为[1，n－i]。记录第i趟排序最后一次交换的位置j，此时表示[j＋1，n]已经有序，下趟排序的区间可以修改为[1，j]，当j小于n－i时，就缩小下趟排序的区间，减少排序的次数，达到优化排序的效果。
【例5】 实现某算法的部分VB 程序段如下：
i＝1
Do While i <＝5
p＝6
For j＝6 To i＋1 Step －1
　If a(j)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)
B
数组元素 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，退出循环。
【变式8】 有如下程序段：
n＝0: i＝2: Last＝6: f＝True
Do While i <＝6 And f
n＝n＋1
f＝False
For j＝1 To Last－1
If a(j)>a(j＋1) Then
　　　　　　t＝a(j): a(j)＝a(j＋1): a(j＋l)＝t
　　　　　　Last＝j
　　　　　　f＝True
End If
Next j
i＝i＋1
Loop
A
数组元素a(1)到a(6) 的值依次为“10，42，36，51，76，87”，经过该程序段“加工”后，下列说法不正确的是(　　)
A.变量n的值为2 B.此过程中数据共需比较9次
C.此过程中数据共需交换1次 D.数组元素a(1)到a(6)的值为升序
解析　本题考查冒泡排序算法的变形。自左向右的冒泡排序，找出每一遍中的最后一次交换，该位置Last后面的数已经有序，第2趟的区间是[1，2]，因此第2趟只比较了1次，共比较6次，在第2趟中没有交换，实现了升序排列。
考点四　双向排序
在每趟排序过程中，可以同时实现两个方向同时排序。
【例6】 小赵对冒泡升序排列算法进行了如下改进：在一趟排序中，同时进行从最后一个元素向前的比较并交换和从第一个元素向后比较并交换，把最小的元素交接到前面，把最大的元素交换到后面，以此类推，直到所有元素的数据按升序排列。小赵编写的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
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 To last－1
If a(i)　　　　t＝a(i): a(i)＝a(i＋1): a(i＋1)＝t
End If
Next i
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或last＝n －start＋1
解析　先用从后往前的冒泡排序，将小的数排到前面，再用从前往后冒泡排序的方法，把较大的数排序后面，直到所有数据有序。从后往前排序的区间是[start，last]，并将左界限向后移。从前往后冒泡的区间是[start，last]，并将右界限向前移，因此last＝last－1，或者是左界限移动前的对称位置的前一位置，因此last＝n －(start－1)＋1＋1。
【变式9】 对n个元素的数组a进行升序排列：第一遍将最小的数移至第1个位置，将最大的数移至第n个位置；第二遍将余下元素中的最小和最大数分别移至第2个和第n－1个位置，以此类推，直到所有数组元素按升序排列。部分代码如下：
m1＝1: m2＝n
Do While m1For i＝m2 To m1＋1 Step －1
If a(i)Next i
________
If a(i)>a(i＋1) Then t＝a(i): a(i)＝a(i＋1): a(i＋1)＝t
Next i
m1＝m1＋1
m2＝m2－1
Loop
要使程序实现上述算法思想，则代码中划线处的语句是(　　)
A.For i＝m1＋1 To m2－1 B.For i＝m2－2 To m1－2 Step －1
C.For i＝m1＋2 To m2－2 D.For i＝m2－1 To m1＋1 Step －1
解析　本题考核的知识点是冒泡排序。第1个For结构是在区间[m1，m2]中，相邻两个数组元素a(i)和a(i－1)比较，实现从后往前冒泡升序排列，因此内循环的开始位置是m2，结束位置是m1＋1，实现了m1位置数据有序。第2个For结构是在区间[m1＋1，m2]中，相邻两个数组元素a(i)和a(i＋1)比较，实现从前往后冒泡升序排列，因此内循环的开始位置是m1＋1，结束位置是m2－1，实现了m2位置数据有序。接着m1向后移，m2向前移动，仍旧在区间[m1，m2]中排序。
A
【变式10】 有如下VB程序段：
k＝1: start＝1: iend＝8: flag＝1
Do While k <＝3
For i＝start To iend－flag Step f1ag
If a(i)>a(i＋flag) Then
　　　　t＝a(i): a(i)＝a(i＋flag): a(i＋flag)＝t
End If
Next i
iend＝iend－flag: flag＝－flag: k＝k＋1
t＝start: start＝iend: iend＝t
Loop
For i＝1 To 8
List1.AddItem Str(a(i))
Next i
B
已知a(1)到a(8)的值是39，18，24，14，2，76，65，59，运行之后a(1)到a(8)的值是(　　)
A.65 39 18 2 14 24 59 76 B.65 18 14 2 24 39 59 76
C.65 18 2 14 24 39 59 76 D.65 18 14 24 2 39 59 76
解析　每趟排序实现从前往后升序排列，把最大的数交换到最后面；接着右界限向前移，改变排序方向进行降序排列，把区间内的最大值移动到最前面。重复以上操作3次。
考点五　冒泡排序过程中去重
从前往后冒泡，后面的数据先有序，若出现两个相同数时，把前面的数替代重复的数，并更新排序的开头位置。从后往前冒泡，前面的数据先有序，若出现两个相同数时，把后面的数替代重复的数，并更新排序的结束位置。
【例7】 小李基于冒泡排序算法编写一个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
　t＝a(j)：a(j)＝a(j－1)：a(j－1)＝t
ElseIf a(j)＝a(j－1) Then ′若相邻数据相等，进行剔除处理
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
答案　(1)a(j)a(j)　或其他等价表达式　(2)a(j)＝a(bottom)　或其他等价语句
解析　本题考核从后往前冒泡的算法思想。从后往前冒泡，前面的数据先有序，当两次比较的数据a(j－1)和a(j)中相等时，a(j－1)可能已经有序，因此用最后一个数据替换a(j)，同时数据的有效长度bottom少1个。
【变式11】 小李基于冒泡排序算法编写一个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
答案　①j＝top　②a(j)＝a(top)
解析　从语句Do While j <＝n－i来看，属于从前往后冒泡，比较的对象是a(j)和a(j＋1)，因此数据从后面开始有序，当两个数据是重复时，把开头的数据替换a(j)，继续排序，变量top表示不重复数据的开始位置，j的初值从top开始。
考点六　多条件或多关键字冒泡
类似Excel中的多关键字进行排序，即当主键字相同时，按次要关键进行交换。也可能是需先满足某个条件，再进行排序。
【例8】 有一组正整数，要求仅对其中的奇数进行升序排序。排序后在列表框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
　　　　　tmp＝a(j) : a(j)＝a(j－1) : a(j－1)＝tmp
　　　　　t＝t＋1
　　　　End If
End If
Next j
i＝i＋1
Loop
For i＝1 to m
List2.AddItem Str(a(i))
Next i
List2.AddItem ”一共交换了” & t & ”次”
End Sub
答案　(1)a(j)解析　这是典型的冒泡排序，但只要求对奇数进行排序，因此当奇数与偶数比较时，把偶数换到后面。M表示奇数的数量。
【变式12】 使用冒泡排序算法对数组排序，要求奇数和偶数各自按升序排序，其中奇数在前，偶数在后。例如将数组a＝(4，5，2，9，6，7，10，3，8，1)，排序成a＝(1，3，5，7，9，2，4，6，8，10)。实现上述功能的VB程序如下，请将缺失的代码补充完整。
Private Sub Command1_Click()
Dim i As Integer，j As Integer，t As Integer
For i＝1 To n－1
For j＝n To____①____
　　　　If (a(j) Mod 2＝a(j－1) Mod 2 And____②____) Or (___③___) Then
　　　　　　　　t＝a(j): a(j)＝a(j－1): a(j－1)＝t
　　　　End If
Next j
Next i
End Sub
答案　①i＋1 Step －1　②a(j)a(j－1) Mod 2
解析　第1空考查内层循环变量j的扫描范围。第2和3空考查判断条件，即何时交换a(j)和a(j－1)的值，当a(j)和a(j－1)的奇偶性相同，且a(j)a(j－1) Mod 2时，也需要交换二者的值。
考点七　奇偶位分别冒泡排序
奇数位的下标分别1，3，5……，偶数位的下标分别2，4，6……，若i Mod 2＝1，则前一个奇数和后一个奇数的位置是i－2或i＋2，同理偶数的步长也是2。可以按奇数位和偶数位分别排序。
【例9】 有如下VB程序段：
a(1)＝12: a(2)＝30: a(3)＝44: a(4)＝46: a(5)＝19: a(6)＝34
cp＝0: ex＝0: k＝1: s＝””
For i＝1 To 2
For j＝1 To 6－i*2
cp＝cp＋1
If a(j)*k　　　　t＝a(j)：a(j)＝a(j＋2): a(j＋2)＝t
　　　　ex＝ex＋1
End If
k＝－k
Next j
Next i
For i＝1 To 6
s＝s＋Trim(Str(a(i))　′Trim函数功能是去除字符串前后空格
Next i
D
执行该程序段后，下列说法正确的是(　　)
A.cp的值为3 B.ex的值为6
C.k的值为－1 D.s的值为 ”443019341246”
解析　从比较和交换对象a(j)和a(j＋2)来看，实现奇数位和偶数位分别排序，k的变化规律为1，－1，1，－1……，当j是奇数是k＝1，当j是偶数时，k＝－1，因此奇数位是降序，偶数位上是升序，排序结果为44，30，19，34，12，46。6个数字分为两组，只需排2趟，整个数组就有序。cp是比较次数，当i＝1时，j循环了4次，当i＝2时，j循环了2次，共比较6次。j的循环次是偶数次，因此k的值为1。
A
1.有如下程序段：
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
解析　本题考核的是从后往前冒泡排序的算法思想。分析本题程序段，外层循环到2，说明只进行了两遍排序。第1遍排序a(5)到a(2)依次与a(1)比较，较大数与a(1)交换，结果为：77，24，45，16，33；第2遍排序a(5)到a(3)依次与a(2)比较，较大数与a(2)交换，结果为：77，45，33，16，24。
B
2.(2020·4月G20联盟)有一个数组采用冒泡排序，第1遍排序后的结果为：3，18，5，35，8，9，11，13，32，那么该数组的原始顺序不可能是(　　)
A.18，5，35，8，9，11，3，13，32
B.3，18，5，35，13，11，32，8，9
C.18，5，35，3，8，9，11，13，32
D.18，5，35，8，9，11，13，32，3
解析　本题主要考查冒泡排序。第1趟排序后最大值在中间，最小值在最左侧，是对原始数据进行了从后往前的升序排列，按此排序方式，只有B项符合要求。
B
3.(2020·5月七彩阳光)分别采用选择排序和冒泡排序对数据序列“15 89 60 34 10 28 70”完成升序排序，则在两种排序方法过程中，数据“60”发生交换的次数分别可能为(　　)
A.3 3 B.2 4 C.21 4 D.3 4
解析　本题主要考查选择排序和冒泡排序的算法思想。选择排序中，第一趟15与10交换，第二趟89与15交换，第三趟60与28交换，第四趟34不交换，第五趟81与60交换，第六趟81和70交换，60被交换了两次；冒泡排序中第一趟排序结果为10，15，89，60，34，28，70，60被交换1次，第二趟排序结果为10，15，28，89，60，34，70，60被交换1次，第三趟排序结果为10，15，28，34，89，60，70，60被交换1次，第四趟排序结果为10，15，28，34，60，89，70，60被交换1次，此后的交换与60无关，60共被交换4次。
4.(2020·9月山水联盟)有如下VB程序段：
C
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.74，32，66，46，38，28
解析　本题主要考查随机数与冒泡排序。a数组中的值为[10，98]之间的偶数，可将A项排除，对a数组中值使用冒泡排序算法进行一定范围内的排序，For i＝1 To 2表示进行了两趟排序，For j＝2 To 6－i表示从前往后冒，根据比较的数为a(j)与a(j－1)，可知排序范围为a(1)到a(5)，第6个数不参加排序，If a(j)\10>a(j－1)\10对数组中值的十位数进行比较后降序排列，根据分析可知，a(1)到a(6)中的值，a(6)不参与排序，a(5)十位数上的值必然小于等于a(1)到a(4)十位数上的值，a(4)十位数上的值必然小于等于a(1)到a(3)十位数上的值，可排除BD，只有C项满足要求。
5.(2020·1月余杭高中)有如下VB程序段：
Dim a(1 To 5) As Integer，s As String
a(1)＝77: a(2)＝73: a(3)＝87: a(4)＝80: a(5)＝66
i＝1: n＝5
Do While i <＝3
j＝1
Do While j <＝n－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
s＝Str(a(i))＋s
i＝i＋1
Loop
Text1.Text＝s
该程序段运行后，文本框Text1中显示的内容是(　　)
A.77　66　73 B.77　77　73
C.73　77　77 D.73　66　77
解析　本题主要考查冒泡排序的程序实现。从比较对象来看，该算法是从前往后进行了3趟从小到大的排序，第1趟排序的结果分别为73，77，80，66，87，第2趟为73，77，66，80，87，第3趟为73，66，77，80，87。再把每趟的a(i)值反向连接。
B
6.VB程序段如下：
exchange＝0
last_change＝8
Do While last_change>1
current＝1
For j＝1 To last_change－1
If a(j)　　　　exchange＝exchange＋1
　　　　tmp＝a(j)：a(j)＝a(j＋1)：a(j＋1)＝tmp
　　　　　　current＝j
End If
Next j
last_change＝current
Loop
数组元素a(1)到a(8)的值依次为“15，13，20，14，12，9，5，1”，执行该程序段，exchange的值为(　　)
A.2 B.3 C.4 D.5
解析　j表示比较的位置，从前向后比较，条件a(j)B
7.数组a中的n个元素经排序生成左右交替上升数据序列的VB程序段如下：
If d(j)　　　　t＝d(j): d(j)＝d(j＋1): d(j＋1)＝t
End If
Next j
Next i
方框中的代码由以下三部分组成：①n－i＋1 ②n\2 ③n－i
代码顺序正确的选项是(　　)
A.②①③ B.①②③ C.②③① D.③②①
解析　每趟实现两个数据有序，只需排一半趟数。每趟的左边界是i，右边界是n－i＋1。
A
8.(2020·4月G20联盟)某同学设计了一个排序算法，先将数组a中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理，直至所有元素按降序排列。算法的VB程序段如下：待排序数据已存储在数组a中(a(1)～a(n) )
For i＝1 To n－2
k＝i
For ______①____
If a(j)>a(k) Then k＝j
Next j
If k <>i Then t＝a(i): a(i)＝a(k): a(k)＝t
Next i
For i＝1 To n\2
j＝2*i－1
If a(j)Next i
For i＝____②____
t＝a(i): j＝i－1
Do While t>a(j)
a(j＋1)＝a(j): j＝j－1
Loop
____③____
Next i
上述程序段中3处方框处的代码分别为(　　)
A.①i＋1 To n Step 2　②2 To n Step 2　③a(j＋1)＝t
B.①i＋2 To n Step 2　②3 To n Step 2　③a(j＋1)＝t
C.①i＋2 To n Step 2　②2 To n Step 2　③a(j)＝t
D.①i＋1 To n Step 2　②3 To n Step 2　③a(j)＝t
B
解析　本题主要考查选择排序、冒泡排序、插入排序。第一段for循环是通过选择排序进行奇数位和偶数位分别进行排序，故被比较位置j的范围i＋2 To n Step 2，第二段for循环的功能是将数组两两分组，通过冒泡排序使每组中的奇数位大于偶数位，最后一段for是通过插入排序使所有数据有序，通过前面的两段排序，可能还存在奇数位比前面的偶数位小的情况，前两位通过第二段排序肯定有序，插入排序可从第三位置开始进行比较，找到该位置值应插入的位置，而偶数位肯定比前面的奇数位小，也必然比偶数位小，不需再进行比较，do循环结束时j的值为从后往前第一个比插入值大的位置，则新插入的位置为j＋1。
9.有如下程序段：
D
a(1)＝3: a(2)＝2: a(3)＝7: a(4)＝5: a(5)＝1
For i＝5 To 2 Step －1
For j＝1 To i－1
If a(j)>a(j＋1)＋Int(Rnd*2) Then
　　　　t＝a(j): a(j)＝a(j＋1): a(j＋1)＝t
End If
Next j
Next i
程序运行后，a(1)到 a(5)的值不可能是(　　)
A.1 2 3 5 7 B.3 2 1 5 7 C.2 1 3 5 7 D.1 2 5 3 74
解析　本题考核的知识点是冒泡排序算法的基本思想。交换的条件是该数比他后面的数＋0或＋1大，那么就要交换，意味着他等于后面的数或等于后面的数＋1，也可以不用交换；经过排序后，他比他前面的第1个数相等或小1，但不可能比他前面的数小2及以上。B选项1比2小1，2比3小1。C选项1比2小1，D选项，3比5小2，不符合要求。
10.有如下VB程序段：
A
t＝Int(Rnd*4＋2)
For i＝1 To 6－t
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
End If
Next j
Next i
数组元素a(1)到a(6)的值依次为“9，4，5，6，7，1”，执行该程序段后，a(1)～a(6)各元素值不可能的是(　　)
A.9，4，7，5，6，1 B.9，7，4，6，5，1
C.9，7，6，4，5，1 D.9，7，6，5，4，1
解析　产生t值为2，3，4，5，那么6－t的值为1，2，3，4。对数组分别进行从后往前冒泡，1－4次，不可能得到A选项。