资源简介 第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 jNext 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 IfNext jNext 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 jNext 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) = tempEnd If Next jNext i一、冒泡排序算法思想理解冒泡排序的基本思想,学会将待排数据按照冒泡算法思想进行手工模拟排序。【典例1】 使用冒泡排序对下表中9个数据进行排序,排序过程如下所示:初始数据1005080706035908525第1遍2510050807060359085第2遍2535100508070608590第3遍则第三遍的排序结果为( )A.25,35,50,60,100,80,70,85,90B.25,35,50,100,60,80,70,85,90C.25,35,50,100,80,70,60,85,90D.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 -1If a(j)>a(j-1) Then End If Next jNext i下列说法正确的是( )A.升序排序,实线框中的语句共执行了8次B.升序排序,实线框中的语句共执行了10次C.降序排序,实线框中的语句共执行了8次D.降序排序,实线框中的语句共执行了10次解析 本题主要考查的是冒泡排序。根据语句“If a(j)>a(j-1)Then”可知,排序方式为从大小到排序(降序),排序过程如下:初始数据545116930交换次数第1遍5154301694第2遍5130541692第3遍5130165492数据交换次数为4+2+2=8次,因此答案为C。答案 C【方法总结】 冒泡排序是通过相邻数据两两比较,可以从前往后进行比较,也可以从后往前进行比较,通过If语句中表达式确定排序的升降性。二、冒泡排序算法实例应用【典例2】 某VB程序段如下:s = “ ”For i = 1 To 3For j = 7 To i + 1 Step -1If a(j) < a(j - 1) Then k = a(j): a(j) = a(j - 1): a(j - 1) = kEnd IfNext js = s + Str(a(i))Next iText1.Text = s数组元素a(1)到a(7)的初始数据依次为“3,9,1,5,8,6,2”,经过该程序段“加工”后,文本框Text1中显示的内容是( ) A.1 2 3 B.9 8 6C.3 9 1 D.8 6 2解析 本题考查的是冒泡排序的算法实现。此题程序的功能是求3遍冒泡排序(升序)后数据序列中前三个数的情况,因此前三个数为1,2,3。答案 A【变式训练】 使用冒泡排序对数组a中的数据进行排序,程序段如下:s = “ ”For i = 1 To 7For j = 1 To 8 - iIf a(j) < a(j + 1) Then k = a(j): a(j) = a(j + 1): a(j + 1) = kEnd IfNext jNext 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 __________②________Thenk=d(j):d(j)=d(j+1):d(j+1)=k End If Next jNext 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。答案 D2.有如下VB程序段:For i =1 To 3For j= 5 To i Step -1If a(j) < a(j+1) Then k = a(j):a(j)= a(j+1):a(j+1)= kEnd IfNext jList1.AddItem Str(a(i))Next j数组元素a(1)到a(6)的数据依次为“1,5,7,6,9,3”,经过该程序段加工后,列表框List1中显示( )A.9、7、6 B.1、3、5C.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个数。答案 A3.n个数据的冒泡排序需要经过n-1遍加工,每一遍加工自下而上比较相邻两个数据,把较大者交换到上面。小刘发现:当某一遍加工过程中没有数据交换,说明数据已经有序,无需进一步加工。为此,小刘对算法进行优化,编写了一个VB程序,功能如下:运行程序时,在列表框List1中显示排序前数据,单击“排序”按钮Command1,在列表框List2 中显示这些数据按升序排序后的结果,在标签Label3中显示排序过程的加工遍数,在标签Label4中显示排序过程的数据交换次数。运行效果如下图所示。实现上述功能的VB代码如下,但加框处代码有错,请改正。Dim a(1 To 8)As IntegerDim n As IntegerPrivate Sub Form_Load() ′n=8,排序前数据存储在数组a中,并在列表框List1中显示 ′代码略End SubPrivate Sub Command1_Click() Dim i As Integer, j As Integer, t As Integer, c As Integer Dim flag As Boolean For i = 1 To nList1.AddItem Str(a(i)) Next i i = 1 flag = False Do While ′(1)flag = TrueFor j = n To i + 1 Step -1 If a(j) > a(j - 1) Thent = a(j): a(j) = a(j - 1): a(j - 1) = t c = c + 1 flag = False End IfNext ji = i + 1 Loop Label3.Caption = “排序过程的加工遍数为” + ′(2) Label4.Caption = “排序过程共数据交换次数为” + Str(c) For i = 1 To nList2.AddItem Str(a(i)) Next iEnd 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 = 0For i =1 To 4yes=FalseFor j=5 To i+1 Step -1If a(j)>a(i) Then yes=True:tot=tot+1 t=a(j):a(j)=a(i):a(i)=tEnd IfNext jIf yes=False Then Exit ForNext 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时,没有交换。答案 B2.有8个数据100、46、39、85、11、10、66、90依次存放在数组元素a(1)到a(8)中,部分VB程序段如下所示:n = Val(Text1.Text)x = 0For i = 1 To n - 1 For j = 8 To i + 1 Step -1If a(j) > a(j - 1) Then tp = a(j): a(j) = a(j - 1): a(j - 1) = tp x = x + 1End If Next jNext iText2.Text = Str(x)程序执行时,在文本框Text1中输入“3”,则文本框Text2输出的值是( )A.6 B.10 C.11 D.12解析 本题主要考查的是冒泡排序算法。本程序的功能是求两遍排序完成时,共进行的数据交换的次数。第一遍排序完成时,需交换6次,第二遍排序完成时,需交换4次,两遍排序完成时,共进行的数据交换的次数为6+4=10,因此答案为B。答案 B3.如下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 10d(i) = Int(Rnd * 100 + 1) Next i st = “ ” For i = 1 To 3For j = 1 To 10 - i If d(j) > d(j + 1) Thentemp = d(j): d(j) = d(j + 1): d(j + 1) = temp End IfNext jst = Str(d(j)) + st Next i Text1.Text = stEnd Sub程序运行时,生成的10个随机整数依次为“1,18,3,66,56,77,85,6,7,12”,则在文本框Text1中显示的内容是( )A.1 3 6 B.6 3 1C.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 IntegerDim n As IntegerPrivate 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 8List1.AddItem a(i) Next iEnd SubPrivate 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 - 1For 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 IfNext j Next iLabel1.Caption = “位置变化情况:” + s For i = 1 To nList2.AddItem Str(a(i)) Next iEnd 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 Then5.下列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 FunctionPrivate 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 Thenn = n + 1num(n) = xList1.AddItem Str(num(n)) End If LoopEnd SubPrivate 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 nIf ____③____Then k = k + 1Else If k > max Then max = k: maxi = i - 1 k = 1End If Next i For i =____④____To maxians = ans + Str(num(i)) Next i Text1.Text = ansEnd 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 jNext 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 IfNext jNext 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 jNext 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) = tempEnd If Next jNext i一、冒泡排序算法思想理解冒泡排序的基本思想,学会将待排数据按照冒泡算法思想进行手工模拟排序。【典例1】 使用冒泡排序对下表中9个数据进行排序,排序过程如下所示:则第三遍的排序结果为( )A.25,35,50,60,100,80,70,85,90B.25,35,50,100,60,80,70,85,90C.25,35,50,100,80,70,60,85,90D.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 jNext 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 iText1.Text = s数组元素a(1)到a(7)的初始数据依次为“3,9,1,5,8,6,2”,经过该程序段“加工”后,文本框Text1中显示的内容是( )A.1 2 3 B.9 8 6C.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 jNext 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【方法总结】 在掌握冒泡排序常规算法的基础上,还要对冒泡排序的各种变式进行研究,做到举一反三,触类旁通。 展开更多...... 收起↑ 资源列表 第2节 冒泡排序及程序实现.doc 第五单元第2节 冒泡排序及程序实现.pptx