冒泡排序及优化练习ppt课件.pptx
2020,冒泡排序及优化,延迟符,冒泡排序应用,冒泡也有变式，即将数组元素进行两两比较，若相邻两个元素中的数据不符合排序，就交换位置。 例1： 某数组c共由4个元素构成，每个元素的值如下表所示：,采用冒泡排序思想进行升序排序，从最下面的一个元素起，自下而上的比较相邻两个元素中的数据，整个排序过程如下所示：,冒泡排序应用,23,15,38,30,冒泡排序应用,第一趟加工处理过程：,第一趟加工共比较3次，处理完成后，最小的元素15存储在了c(1)中。第二趟加工处理过程：,第二趟加工共比较2次，处理完成后，第2个最小的元素23存储在了c(2)中。,延迟符,冒泡排序应用,第三趟加工处理过程：,第三趟加工共比较1次，处理完成后，第3个小的元素32存储在了c(3)中。 4个元素共需进行3趟加工处理，总的比较次数为3216次。对n个元素的数组，用冒泡法进行排序时，共需比较_次。,n(n-1)/2,冒泡排序算法,4个元素进行冒泡排序时，需要三趟，用i表示趟数,i 1,i=3?,结束,Y,i i+1,N,进行第i趟冒泡排序,开始,4个元素进行冒泡排序时，需要三趟，用i表示趟数,i 1,i=3?,结束,Y,i i+1,N,j表示元素的位置a(j)与a(j-1)是相邻的元素,j=i+1?,开始,冒泡排序算法,延迟符,冒泡排序算法的程序实现,冒泡排序程序的实现可用双重For循环来实现，外层For循环控制是第几遍加工 ，内层For循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化(每趟减少一个)，故内层For循环变量的下界由外层循环变量决定。 现有n个数据，分别存放在数组变量a(1 To n)当中，用冒泡排序算法表示结构如下：,延迟符,冒泡排序算法的基本思想,冒泡排序的代码如下(升序)：For i=1 to n-1 n个数需要n-1次排序 For j=n to i+1 step -1 从后往前，两两比较，一直到第i+1个数 If a(j) a(j-1)。,用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。, 49,38,65,97,76,13,27,49 ,分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：,对比原数据经过第一趟排序，实现了什么目的？,第一趟排序，一共进行了多少次比较？,4938,交换位置,原数据和序号,第一趟排序的步骤：,经过第一趟排序，把最大的数沉到最底了！,4965, 保持不变,6597, 保持不变,9776, 交换位置,9713, 交换位置,9727, 交换位置,9749, 交换位置,经过第二趟排序，实现了什么目的？,经过第二趟排序，把第二大的数沉到倒数第二个位置了!,3849,保持不变,第一趟排序后的数据和序号,第二趟排序的步骤：,4965, 保持不变,6576, 保持不变,7613, 交换位置,7627, 交换位置,7649, 交换位置,7697, 保持不变,观察原数据与第一、二趟排序后的数据,问：为了使这一组无序数组完全按照要求排成从小到大我们还需不需要再继续排序呢？,问：那么我们预计最多一共要经过多少次排序呢？,初始,1趟,2趟,3趟,4趟,5趟,6趟,7趟,延迟符,冒泡排序算法的基本思想,冒泡排序的代码如下(升序)：For i=1 to n-1 n个数需要n-1次排序 For j=1 to n-i 从前往后，两两比较，一直到第n-i个数 If a(j) a(j+1) then 比较相邻的两个数 temp=a(j) : a(j)=a(j+1) : a(j+1)=temp 小的在后面，则交换 End If Next jNext i(注)：从小到大排序，If语句中条件表达式为：a(j)a(j+1)； 从大到小排序，If语句中条件表达式为：a(j)a(j+1)。,1. 有以下VB 程序段For i = 1 To 3 For j = i To 5 If a(j) a(j + 1) Then t = a(j): a(j) = a(j+1): a(j+1)=t End If Next j List1.AddItem Str(a(i)Next i a(1)到a(6)的初始值依次为“865793 ”，经过该程序段“加工”后，列表框List1中显示的是（ ）A8 7 6 B8 7 9 C6 5 3 D5 6 7,C,2.有以下VB 程序段For i = 1 To 2 For j = 1 To 5-i If a(j+1) a(j) Then t = a(j): a(j) = a(j+1): a(j+1) = t End If Next jNext i数据“56,23,78,11,8”依次存放在数组a（1）到a（5）中，执行下列VB程序段后，数组a（1）到a（5）中的数据依次为（ ）A. 8,11,23,56,78 B. 23,11,8,56,78C. 11,8,23,56,78 D. 8,11,56,23,78,B,3有如下VB 程序段：For i = 6 To 4 Step -1 j = 1 Do While j a(j + 1) Then t = a(j): a(j) = a(j + 1): a(j + 1) = t End If j = j + 1 LoopNext i数组元素a(1)到a(6)的值依次为“26,13,23,18,7,14”，执行该程序段后，数组元素a(1)到a(6)的值依次为（ ）A26,13,23,18,7,14 B13,7,14,18,23,26C7,13,14,18,23,26 D26,23,18,14,13,7,B,4.冒泡排序在某一遍加工过程中没有数据交换时，说明数据已经有序，优化程序段如下 i = 1: flag = True Do While i a(j - 1) Then t = a(j): a(j)=a(j-1): a(j-1) = t flag = True End If Next j i = i + 1 Loop 数组元素a(1)到a(5)的值依次为“48, 36, 24, 97，77”，经过该程序段“加工”后，变量i的值是( ) A. 1 B.2 C. 3 D. 4,D,5有如下程序段： i = 1 Do While i = 4 And flag(i) = False 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)的值依次为“27，5，25, 36,78”，数组flag的初值均为False，经过该程序段“加工”后，数组元素放flag(1)到flag(5)中值为True的个数是( ) A. 1 B. 2 C. 3 D. 4,B,6.下面程序是一个改进过的冒泡排序：Dim a(1 To 5) As Integera(1)=5: a(2)=10: a(3) = 9: a(4)=3: a(5)=7n = 5: p = 0swap = TrueDo While swap = True swap = False For i = 1 To n -1 If a(i) a(i + 1) Then t= a(i): a(i) = a(i+1): a(i+1)=t swap = True End If Next i If swap = True Then p = p + 1LoopText1.Text = p该程序段执行后，在文本框Text1中显示的内容为( )A.1 B.2 C.3 D.4,C,7. 已知字符串数组a（1）到a（6）的原始数据为”118”，”36”，”98”，”15”，”88”，”2”，为了对该数组进行排序操作，小吴编写了以下VB程序： For i=1 to 3 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 Next j Next i 则程序运行之后，数组a（1）到a（6）的值依次为（ ） A. ”118”，”15”，”2”，”36”，”88”，”98” B. ”118”，”15”，”36”，”88”，”98”，”2” C. ”2”，”15”，”36”，”118”，”88”，”98” D. ”2”，”15”，”36”，”88”，”98”，”118”,A,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 LoopNext iFor i = 3 To 6 s = s + a(i)Next iLabel1.Caption = Str(s)已知数组元素a(1)到a(7)的值依次为“8,2,3,7,10,6,5”，则执行该程序段后，标签Label1中显示的是( )A21 B26 C41 D18,A,9.n个数据的冒泡升序排序需要经过n-1遍的加工，每一遍加工自下而上比较相邻两个数据，把较小者交换到上面，在第i遍加工过程中需要进行n-i对数据的比较。在某些情况下，第i遍加工过程中，在上面部分较小数据已经有序情况下，不需要再进行n-i对数据的比较。如对“17，18，19，24，23，20”这6个数据排序中，第1遍排序结束后数据为“17，18，19，20，24，23”，第2遍排序时不再需要对20及其前面4个数据进行比较。以下程序实现了冒泡排序的优化，在划处填入合适的代码。,Dim n As IntegerDim a(1 To 100) As Integer n = 10，排序前生成的数据存储在数组a 中，并在列表框List1 中显示代码略Private Sub Command1_Click()Dim i As Integer, j As Integer, start As Integer, t As Integeri = 2 Do While i =n start = n For j = n To i Step -1 If _Then t = a(j) : a(j) = a(j -1) : a(j -1) = t _ End If Next j i= start + 1 LoopFor i = 1 To n List2.AddItem _ Next iEnd Sub,a(j)a(j-1),Start=j,Str(a(i),10.冒泡算法,当数据已经有序时就停止加工，为此编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Command1，在列表框List2 中显示按升序排序后的结果，在标签Label1中显示排序加工趟数、在标签Label2中显示数据交换次数。运行效果如图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。,Const n = 10Dim a(1 To n) As Integer排序前数据存储在数组a中，并在Listl中显示，代码略Private Sub Command1_Click()Dim flag As Boolean,x As Integer,y As Integerx = 0: y = 0: flag = True:i = 1Do While i a(j-1) Then t = a(j):a(j) = a(j -1):a(j -1) = t flag = True x = 1 End If Next j y = y + 1 i = n -1LoopLabel1.Caption = 经过 + Str(y) + 趟排序数据有序！Label2.Caption = 数据总共交互 + Str(x) + 次！“,For i = 1 To n List2.AddItem Str(a(i)Next iEnd Sub,a(j)a(j-1),x=x+1,i=i+1,谢,谢,观,看,
