《冒泡排序及优化练习ppt课件.pptx》由会员分享，可在线阅读，更多相关《冒泡排序及优化练习ppt课件.pptx（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2020冒泡排序及优化2冒泡排序应用 冒泡也有变式，即将数组元素进行两两比较，若相邻两个元素中的数据不符合排序，就交换位置。 例1： 某数组c共由4个元素构成，每个元素的值如下表所示： 数组元素数组元素c(1)c(2)c(3)c(4)值值23383015 采用冒泡排序思想进行升序排序，从最下面的一个元素起，自下而上的比较相邻两个元素中的数据，整个排序过程如下所示：3冒泡排序应用23数组元素数组元素c(1)c(2)c(3)c(4)值值233830151538304冒泡排序应用 第一趟加工处理过程： 第一趟加工共比较3次，处理完成后，最小的元素15存储在了c(1)中。第二趟加工处理过程： 第二趟加
2、工共比较2次，处理完成后，第2个最小的元素23存储在了c(2)中。5冒泡排序应用第三趟加工处理过程： 第三趟加工共比较1次，处理完成后，第3个小的元素32存储在了c(3)中。 4个元素共需进行3趟加工处理，总的比较次数为3216次。对n个元素的数组，用冒泡法进行排序时，共需比较_次。n(n-1)/2n4 4个元素进行冒泡排序时，个元素进行冒泡排序时，需要三趟，用需要三趟，用i i表示趟数表示趟数i 1i=3?结束Yi i+1N进行第i趟冒泡排序开始n4 4个元素进行冒泡排序时，需个元素进行冒泡排序时，需要三趟，用要三趟，用i i表示趟数表示趟数i 1i=3?结束Yi i+1Nj 4比较a(j)
3、和a(j-1)如果a(j)=i+1?开始8冒泡排序算法的程序实现 冒泡排序程序的实现可用双重For循环来实现，外层外层ForFor循环控制是第几循环控制是第几遍加工遍加工 ，内层内层ForFor循环控制进行排序的数组元素下标的变化范围循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化(每趟减少一个)，故内层For循环变量的下界由外层循环变量决定。 现有n个数据，分别存放在数组变量a(1 To n)当中，用冒泡排序算法表示结构如下： 9冒泡排序算法的基本思想冒泡排序的代码如下(升序)：For i=1 to n-1 n个数需要个数需要n-1次排序次排序 For
4、j=n to i+1 step -1 从后往前从后往前，两两比较，一直到第，两两比较，一直到第i+1个数个数 If a(j) a(j-1) then 比较相邻的两个数比较相邻的两个数 temp=a(j-1) : a(j-1)=a(j) : a(j)=temp 小的在后面，则交换小的在后面，则交换 End If Next jNext i(注)：从小到大排序，If语句中条件表达式为：a(j)a(j-1)。用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。 49,38,65,97,76,13,27,49 分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：4938,交换位置原数据和
5、序号第一趟排序的步骤：4965, 保持不变6576, 交换位置9713, 交换位置9727, 交换位置9749, 交换位置3849,保持不变第一趟排序后的数据和序号第二趟排序的步骤：4965, 保持不变6513, 交换位置7627, 交换位置7649, 交换位置76 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(
6、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 7C2.有以下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
7、,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,78B3有如下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”，执行该程序段后，
8、数组元素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,7B4.冒泡排序在某一遍加工过程中没有数据交换时，说明数据已经有序，优化程序段如下 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”，经过该程序段“加工”后
9、，变量i的值是( ) A. 1 B.2 C. 3 D. 4 D5有如下程序段： i = 1 Do While i = 4 And flag(i) = False For j = 5 To i + 1 Step -1 If a(j) 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.4C7. 已知字符串数组a（1）到a（6）的原
10、始数据为”118”，”36”，”98”，”15”，”88”，”2”，为了对该数组进行排序操作，小吴编写了以下VB程序： For i=1 to 3 For j=6 to i+1 step -1 If a(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,
11、3,7,10,6,5”，则执行该程序段后，标签Label1中显示的是( )A21 B26 C41 D18A9.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
12、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
13、If Next j i= start + 1 LoopFor i = 1 To n List2.AddItem _ Next iEnd Suba(j)a(j-1)Start=jStr(a(i)10.冒泡算法,当数据已经有序时就停止加工，为此编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Command1，在列表框List2 中显示按升序排序后的结果，在标签Label1中显示排序加工趟数、在标签Label2中显示数据交换次数。运行效果如图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。Const n = 10Dim a(1 To n) A
14、s 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 = n -1 And flag flag = False 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 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 Suba(j)a(j-1)x=x+1i=i+1谢谢观看