第2节 冒泡排序及程序实现
考试内容
考试要求
冒泡排序算法思想
c
冒泡排序程序实现
c
一、冒泡排序算法思想
什么是冒泡排序
将n个数据看作竖向排列的一组数据，每趟排序自下而上对每对相邻数据进行比较，若次序不符合要求就进行交换。每趟排序结束时都能使排序范围内关键字最小的记录像一个气泡一样升到上端的对应位置，整个排序过程共进行n－1趟，依次将关键字最小、次小……的各个数据冒到表的第一个、第二个……位置上。
用冒泡排序对n个数据进行排序时，共需进行n－1趟排序，比较的总次数为。
二、冒泡排序算法框架
约定：对数组d中的n个数据进行升序排序。
(1)从后往前进行比较
For i ＝ 1 To n － 1 ′n个数据进行排序，共需进行n－1趟
For j ＝ n To i ＋ 1 Step － 1 ′第i趟排序时
If d(j) < d(j－1) Then ′符合条件则进行数据交换
交换数据元素d(j)与d(j－1)的值
End If
Next j
Next i
注：若要按降序排列，将程序中的语句“If d(j)d(j －1) Then”即可。
(2)从前往后进行比较
For i ＝ 1 To n － 1 ′n个数据进行排序，共需进行n－1趟
For j ＝ 1 To n － i ′第i趟排序时
If d(j) > d(j＋1) Then ′符合条件则进行数据交换
交换数据元素d(j)与d(j＋1)的值
End If
Next j
Next i
注：若要按降序排列，将程序中的语句“If d(j)>d(j＋1) Then”改为“If d(j)三、冒泡排序程序实现
约定：对数组d中的n个数据进行升序排序。
(1)从后往前进行比较时程序如下：
For i ＝ 1 To n － 1 ′n个数排序共需进行n－1趟
For j ＝ n To i ＋ 1 Step －1 ′第i趟排序时
If d(j) < d(j － 1) Then ′若后面元素小于前面元素时进行交换
temp ＝ d(j)
d(j) ＝ d(j － 1)
d(j － 1) ＝ temp
End If
Next j
Next i
(2)从前往后进行比较时程序如下：
For i ＝ 1 To n － 1 ′n个数排序共需进行n－1趟
For j ＝ 1 To n － i ′第i趟排序时
If d(j) > d(j ＋ 1) Then ′若前面元素大于面元素时进行交换
temp ＝ d(j)
d(j) ＝ d(j ＋ 1)
d(j ＋ 1) ＝ temp
End If
Next j
Next i
一、冒泡排序算法思想
理解冒泡排序的基本思想，学会将待排数据按照冒泡算法思想进行手工模拟排序。
【典例1】 使用冒泡排序对下表中9个数据进行排序，排序过程如下所示：
初始数据
100
50
80
70
60
35
90
85
25
第1遍
25
100
50
80
70
60
35
90
85
第2遍
25
35
100
50
80
70
60
85
90
第3遍
则第三遍的排序结果为( )
A.25，35，50，60，100，80，70，85，90
B.25，35，50，100，60，80，70，85，90
C.25，35，50，100，80，70，60，85，90
D.25，35，50，60，70，80，85，90，100
解析 本题主要考查冒泡排序算法的基本思想。观察第1、2遍的排序结果可知，该冒泡排序采用从后往前两两比较的方式进行升序排序，因此手工模拟可知，第3遍排序后的结果为25，35，50，100，60，80，70，85，90，答案为B。
答案 B
【变式训练】 采用冒泡排序算法对数组a中的6个数据“5，4，51，16，9，30”进行排序，部分程序如下：
For i＝1 To 3
For j＝6 To i＋1 Step －1
If a(j)>a(j－1) Then
End If
Next j
Next i
下列说法正确的是( )
A.升序排序，实线框中的语句共执行了8次
B.升序排序，实线框中的语句共执行了10次
C.降序排序，实线框中的语句共执行了8次
D.降序排序，实线框中的语句共执行了10次
解析 本题主要考查的是冒泡排序。根据语句“If a(j)>a(j－1)Then”可知，排序方式为从大小到排序(降序)，排序过程如下：
初始数据
5
4
51
16
9
30
交换次数
第1遍
51
5
4
30
16
9
4
第2遍
51
30
5
4
16
9
2
第3遍
51
30
16
5
4
9
2
数据交换次数为4＋2＋2＝8次，因此答案为C。
答案 C
【方法总结】 冒泡排序是通过相邻数据两两比较，可以从前往后进行比较，也可以从后往前进行比较，通过If语句中表达式确定排序的升降性。
二、冒泡排序算法实例应用
【典例2】 某VB程序段如下：
s ＝ “ ”
For i ＝ 1 To 3
For j ＝ 7 To i ＋ 1 Step －1
If a(j) < a(j － 1) Then
k ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ k
End If
Next j
s ＝ s ＋ Str(a(i))
Next i
Text1.Text ＝ s
数组元素a(1)到a(7)的初始数据依次为“3，9，1，5，8，6，2”，经过该程序段“加工”后，文本框Text1中显示的内容是( )
A.1 2 3 B.9 8 6
C.3 9 1 D.8 6 2
解析 本题考查的是冒泡排序的算法实现。此题程序的功能是求3遍冒泡排序(升序)后数据序列中前三个数的情况，因此前三个数为1，2，3。
答案 A
【变式训练】 使用冒泡排序对数组a中的数据进行排序，程序段如下：
s ＝ “ ”
For i ＝ 1 To 7
For j ＝ 1 To 8 － 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(8)的初始数据依次为“11，8，21，15，18，16，2，30”，排序完成时，共进行数据交换的次数为( )
A.9 B.10 C.11 D.12
解析 本题考查的是冒泡排序的算法实现。本题使用冒泡排序从前往后相邻数据进行两两比较，进行降序排序，求排序完成时数据交换的总次数。第1遍排序共交换数据5次，第2遍排序共交换数据2次，第3遍排序共交换数据1次，第4遍排序共交换数据1次，第5遍排序共交换数据1次，第6遍排序共交换数据1次，因此，共交换数据次数为5＋2＋1＋1＋1＋1＝11，答案为C。
答案 C
【方法总结】 在掌握冒泡排序常规算法的基础上，还要对冒泡排序的各种变式进行研究，做到举一反三，触类旁通。
1.现有包含10个元素的数组d，使用冒泡排序法对此数组元素进行升序排序，部分VB代码如下：
For i＝1 To 9
For j＝__________①________
If __________②________Then
k＝d(j)：d(j)＝d(j＋1)：d(j＋1)＝k
End If
Next j
Next i
划线①②处应填写的正确语句是( )
A.①i＋1 To n，②d(j)>d(j＋1)
B.①i＋1 To n，②d(j)C.①1 To n－i，②d(j)D.①1 To n－i，②d(j)>d(j＋1)
解析 本题考查冒泡排序算法。交换的数据对为“d(j)与d(j＋1)”，因此可判断相邻元素是从前往后两两比较的，答案为D。
答案 D
2.有如下VB程序段：
For i ＝1 To 3
For j＝ 5 To i Step －1
If a(j) < a(j＋1) Then
k ＝ a(j)：a(j)＝ a(j＋1)：a(j＋1)＝ k
End If
Next j
List1.AddItem Str(a(i))
Next j
数组元素a(1)到a(6)的数据依次为“1，5，7，6，9，3”，经过该程序段加工后，列表框List1中显示( )
A.9、7、6 B.1、3、5
C.9、7、6、1、5、3 D.9、7、6、5、3、1
解析 比较对象为a(j)和a(j＋1)，但j的初值为5，终值为i。每趟比较还是从最后一个位置的元素开始，与他前面的元素比较，当a(j)比他后面元素的小，发生交换，即为降序排列。i从1循环到3，即进行了3趟排序，且只输出前面的3个数。
答案 A
3.n个数据的冒泡排序需要经过n－1遍加工，每一遍加工自下而上比较相邻两个数据，把较大者交换到上面。小刘发现：当某一遍加工过程中没有数据交换，说明数据已经有序，无需进一步加工。为此，小刘对算法进行优化，编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Command1，在列表框List2 中显示这些数据按升序排序后的结果，在标签Label3中显示排序过程的加工遍数，在标签Label4中显示排序过程的数据交换次数。运行效果如下图所示。
实现上述功能的VB代码如下，但加框处代码有错，请改正。
Dim a(1 To 8)As Integer
Dim n As Integer
Private Sub Form_Load()
′n＝8，排序前数据存储在数组a中，并在列表框List1中显示
′代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, t As Integer, c As Integer
Dim flag As Boolean
For i ＝ 1 To n
List1.AddItem Str(a(i))
Next i
i ＝ 1
flag ＝ False
Do While ′(1)
flag ＝ 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
c ＝ c ＋ 1
flag ＝ False
End If
Next j
i ＝ i ＋ 1
Loop
Label3.Caption ＝ “排序过程的加工遍数为” ＋ ′(2)
Label4.Caption ＝ “排序过程共数据交换次数为” ＋ Str(c)
For i ＝ 1 To n
List2.AddItem Str(a(i))
Next i
End Sub
程序中加框(1)处应改正为___________________________________________；
加框(2)处应改正为__________________________________________________。
解析 本题主要考查的是冒泡排序的程序实现。n个数进行排序，共需进行n－1遍(趟)。若进行i遍后数据已经有序，则不需要再进行排序。排序结束的条件的是：排序遍数小于n－1遍，且数据有序。Flag＝True表示数据相邻数据无交换，说明数据已经有序，因此(1)处的语句应更正为：i<＝n－1 And flag＝False或i<＝n－1 And Not flag；变量i存储排序遍数，由于i的初值为1，因此总的排序遍数为i－1，因此(2)处语句更正为Str(i－1)。
答案 (1)i<＝n－1 And flag＝False或i<＝n－1 And Not flag (2)Str(i－1)
基础巩固
1.有如下程序段：
tot ＝ 0
For i ＝1 To 4
yes＝False
For j＝5 To i＋1 Step －1
If a(j)>a(i) Then
yes＝True：tot＝tot＋1
t＝a(j)：a(j)＝a(i)：a(i)＝t
End If
Next j
If yes＝False Then Exit For
Next i
数组元素a(1)到a(5)的值依次为“29，23，9，14，97”，经该程序段“加工”后，tot的值为( )
A.2 B.3
C.4 D.5
解析 比较和交换的对象为a(j)和a(i)，并不属于典型的冒泡算法，是冒泡的一种变式。当yes＝True时，说明已经发生交换，并统计交换次数tot。分i＝1，2，3，4分别进行讨论。当i＝1时，交换的结果为97，23，9，14，29，只交换一次。当i＝2时，交换的结果为97，29，9，14，23，也交换了一次；当i＝3时，交换的结果为97，29，23，14，9，也交换了一次；当i＝4时，没有交换。
答案 B
2.有8个数据100、46、39、85、11、10、66、90依次存放在数组元素a(1)到a(8)中，部分VB程序段如下所示：
n ＝ Val(Text1.Text)
x ＝ 0
For i ＝ 1 To n － 1
For j ＝ 8 To i ＋ 1 Step －1
If a(j) > a(j － 1) Then
tp ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ tp
x ＝ x ＋ 1
End If
Next j
Next i
Text2.Text ＝ Str(x)
程序执行时，在文本框Text1中输入“3”，则文本框Text2输出的值是( )
A.6 B.10
C.11 D.12
解析 本题主要考查的是冒泡排序算法。本程序的功能是求两遍排序完成时，共进行的数据交换的次数。第一遍排序完成时，需交换6次，第二遍排序完成时，需交换4次，两遍排序完成时，共进行的数据交换的次数为6＋4＝10，因此答案为B。
答案 B
3.如下VB程序段：
Private Sub Command1_Click()
Dim i As Integer, j As Integer, temp As Integer, st As String
Dim d(1 To 10) As Integer
For i ＝ 1 To 10
d(i) ＝ Int(Rnd * 100 ＋ 1)
Next i
st ＝ “ ”
For i ＝ 1 To 3
For j ＝ 1 To 10 － i
If d(j) > d(j ＋ 1) Then
temp ＝ d(j): d(j) ＝ d(j ＋ 1): d(j ＋ 1) ＝ temp
End If
Next j
st ＝ Str(d(j)) ＋ st
Next i
Text1.Text ＝ st
End Sub
程序运行时，生成的10个随机整数依次为“1，18，3，66，56，77，85，6，7，12”，则在文本框Text1中显示的内容是( )
A.1 3 6 B.6 3 1
C.85 77 66 D.66 77 85
解析 本题考查的是冒泡排序的算法实现。该程序的功能是对数据使用冒泡排序升序排序3趟，并将每趟得到的最大值存放在字符串st中，需注意的是语句st ＝ Str(d(j)) ＋ st，即将当前得到的最大数拼接在字符串st的前面。因此，三趟排序结束后，变量st的值为“ 66 77 85”，答案为D。
答案 D
能力提升
4.小吴为了研究冒泡排序过程中数据的“移动”情况，编写了一个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
′①
a(j － 1) ＝ a(j)
a(j) ＝ k
′如果pos位置的数据参与交换，则更新pos值，记录pos变化位置
If pos ＝ j Then
pos ＝ j － 1
s ＝ s ＋ “→” ＋ Str(pos)
′②
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)的值；交换变量a(j)和a(j － 1)的值后，该两个元素数据位置发生变化，接下来判断这两个元素的下标是否和pos相同，如果pos和j相同，已经被交换到j－1位置，pos需要更新，否则如果pos和j－1相同，已经被交换到j位置，pos需要更新。
答案 ①k＝a(j－1) ②ElseIf pos ＝ j － 1 Then
5.下列VB程序的功能是：程序运行时，单击“生成数据”按钮Command1后，产生20个[1，200]范围内互不相同的随机整数，并依次显示在列表框List1中；单击“开始处理”按钮Command2，首先将数据从小到大排序，并将排序结果显示在列表框List2中，然后在排序的数据中寻找最长的连续整数段(由连续的整数组成的数据段)，若最长连续整数段有多段，则输出最先找到的数据段，并将结果显示在文本框Text1中。程序运行效果如图所示。
(1)下列有关事件处理过程“Command1_Click()”Do循环中语句“x ＝ Int(Rnd * 200) ＋ 1”执行次数的说法正确的是________(单选，填字母：A.执行19次 / B.执行20次 / C.大于或等于19次)。
(2)请在程序划线处填入合适的代码。
Dim num(0 To 20) As Integer ′存储产生的互不相同的随机整数
Dim n As Integer ′n用于统计已经产生的随机整数个数
Function fx(x As Integer) As Boolean
Dim i As Integer，flag As Boolean
flag＝False
i ＝ n
Do While ____①____
If x < > num(i) Then i ＝ i － 1 Else Exit Do
Loop
If i > 0 Then flag ＝ True
②____
End Function
Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim x As Integer, k As Integer
Randomize ′初始化Rnd函数
n ＝ 1
x ＝ Int(Rnd * 200＋1)
num(1) ＝ x
List1.AddItem Str(num(1))
Do While n <20
x ＝ Int(Rnd * 200＋1)
If fx(x)＝False Then
n ＝ n ＋ 1
num(n) ＝ x
List1.AddItem Str(num(n))
End If
Loop
End Sub
Private Sub Command2_Click()
Dim i As Integer, j As Integer, tt As Integer, max As Integer, maxi As Integer
Dim ans As String
For i ＝ 1 To n － 1
For j ＝ n To i ＋ 1 Step －1
If num(j) < num(j － 1) Then
tt ＝ num(j): num(j) ＝ num(j － 1): num(j － 1) ＝ tt
End If
Next j
Next i
For i ＝ 1 To 20
List2.AddItem Str(num(i))
Next i
max ＝ 1
k ＝ 1
For i ＝ 2 To n
If ____③____Then
k ＝ k ＋ 1
Else
If k > max Then max ＝ k: maxi ＝ i － 1
k ＝ 1
End If
Next i
For i ＝____④____To maxi
ans ＝ ans ＋ Str(num(i))
Next i
Text1.Text ＝ ans
End Sub
解析 判断产生的随机整数x是否已经存在(判重)的方法为：将x分别与已产生的前n－1个数进行比较，若有重复则返回函数值True，否则返回False，因此①处代码为i>＝1或i>0，函数值通过函数名返回，因此②处语句为fx＝flag；③处语句表示判断第i个与第i－1个数是不是连续整数，若是则连续整数个数加1，因此③处语句为num(i) ＝ num(i － 1) ＋ 1；程序④处表示最长连续整数段的范围，结束位置为maxi，长度为k，因此开始位置为maxi － max ＋ 1。
答案 (1)C (2)①i>＝1或i>0 ②fx＝flag ③num(i) ＝ num(i － 1) ＋ 1 ④maxi － max ＋ 1
课件17张PPT。第2节 冒泡排序及程序实现一、冒泡排序算法思想什么是冒泡排序
将n个数据看作竖向排列的一组数据，每趟排序自下而上对每对相邻数据进行比较，若次序不符合要求就进行交换。每趟排序结束时都能使排序范围内关键字最小的记录像一个气泡一样升到上端的对应位置，整个排序过程共进行n－1趟，依次将关键字最小、次小……的各个数据冒到表的第一个、第二个……位置上。二、冒泡排序算法框架约定：对数组d中的n个数据进行升序排序。
(1)从后往前进行比较
For i ＝ 1 To n － 1 ′n个数据进行排序，共需进行n－1趟
For j ＝ n To i ＋ 1 Step － 1 ′第i趟排序时
If d(j) < d(j－1) Then ′符合条件则进行数据交换
交换数据元素d(j)与d(j－1)的值
End If
Next j
Next i注：若要按降序排列，将程序中的语句“If d(j)d(j －1) Then”即可。(2)从前往后进行比较
For i ＝ 1 To n － 1 ′n个数据进行排序，共需进行n－1趟
For j ＝ 1 To n － i ′第i趟排序时
If d(j) > d(j＋1) Then ′符合条件则进行数据交换
交换数据元素d(j)与d(j＋1)的值
End If
Next j
Next i
注：若要按降序排列，将程序中的语句“If d(j)>d(j＋1) Then”改为“If d(j)(1)从后往前进行比较时程序如下：
For i ＝ 1 To n － 1 ′n个数排序共需进行n－1趟
For j ＝ n To i ＋ 1 Step －1 ′第i趟排序时
If d(j) < d(j － 1) Then ′若后面元素小于前面元素时进行交换
temp ＝ d(j)
d(j) ＝ d(j － 1)
d(j － 1) ＝ temp
End If
Next j
Next i(2)从前往后进行比较时程序如下：
For i ＝ 1 To n － 1 ′n个数排序共需进行n－1趟
For j ＝ 1 To n － i ′第i趟排序时
If d(j) > d(j ＋ 1) Then ′若前面元素大于面元素时进行交换
temp ＝ d(j)
d(j) ＝ d(j ＋ 1)
d(j ＋ 1) ＝ temp
End If
Next j
Next i一、冒泡排序算法思想理解冒泡排序的基本思想，学会将待排数据按照冒泡算法思想进行手工模拟排序。【典例1】 使用冒泡排序对下表中9个数据进行排序，排序过程如下所示：则第三遍的排序结果为( )
A.25，35，50，60，100，80，70，85，90
B.25，35，50，100，60，80，70，85，90
C.25，35，50，100，80，70，60，85，90
D.25，35，50，60，70，80，85，90，100
解析 本题主要考查冒泡排序算法的基本思想。观察第1、2遍的排序结果可知，该冒泡排序采用从后往前两两比较的方式进行升序排序，因此手工模拟可知，第3遍排序后的结果为25，35，50，100，60，80，70，85，90，答案为B。
答案 B【变式训练】 采用冒泡排序算法对数组a中的6个数据“5，4，51，16，9，30”进行排序，部分程序如下：For i＝1 To 3
For j＝6 To i＋1 Step －1
If a(j)>a(j－1) Then End If
Next j
Next i下列说法正确的是( )
A.升序排序，实线框中的语句共执行了8次
B.升序排序，实线框中的语句共执行了10次
C.降序排序，实线框中的语句共执行了8次
D.降序排序，实线框中的语句共执行了10次解析 本题主要考查的是冒泡排序。根据语句“If a(j)>a(j－1)Then”可知，排序方式为从大小到排序(降序)，排序过程如下：数据交换次数为4＋2＋2＝8次，因此答案为C。答案 C【方法总结】 冒泡排序是通过相邻数据两两比较，可以从前往后进行比较，也可以从后往前进行比较，通过If语句中表达式确定排序的升降性。二、冒泡排序算法实例应用
【典例2】 某VB程序段如下：s ＝ “ ”
For i ＝ 1 To 3
For j ＝ 7 To i ＋ 1 Step －1
If a(j) < a(j － 1) Then
k ＝ a(j): a(j) ＝ a(j － 1): a(j － 1) ＝ k
End If
Next j
s ＝ s ＋ Str(a(i))
Next i
Text1.Text ＝ s数组元素a(1)到a(7)的初始数据依次为“3，9，1，5，8，6，2”，经过该程序段“加工”后，文本框Text1中显示的内容是( )
A.1 2 3 B.9 8 6
C.3 9 1 D.8 6 2
解析 本题考查的是冒泡排序的算法实现。此题程序的功能是求3遍冒泡排序(升序)后数据序列中前三个数的情况，因此前三个数为1，2，3。
答案 A【变式训练】 使用冒泡排序对数组a中的数据进行排序，程序段如下：s ＝ “ ”
For i ＝ 1 To 7
For j ＝ 1 To 8 － 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(8)的初始数据依次为“11，8，21，15，18，16，2，30”，排序完成时，共进行数据交换的次数为( )
A.9 B.10 C.11 D.12
解析 本题考查的是冒泡排序的算法实现。本题使用冒泡排序从前往后相邻数据进行两两比较，进行降序排序，求排序完成时数据交换的总次数。第1遍排序共交换数据5次，第2遍排序共交换数据2次，第3遍排序共交换数据1次，第4遍排序共交换数据1次，第5遍排序共交换数据1次，第6遍排序共交换数据1次，因此，共交换数据次数为5＋2＋1＋1＋1＋1＝11，答案为C。
答案 C【方法总结】 在掌握冒泡排序常规算法的基础上，还要对冒泡排序的各种变式进行研究，做到举一反三，触类旁通。
