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个最小的元素23存储在了c(2)中。5延迟符冒泡排序应用③第三趟加工处理过程：第三趟加工共比较1次，处理完成后，第3个小的元素32存储在了c(3)中。4个元素共需进行3趟加工处理，总的比较次数为3＋2＋1＝6次。对n个元素的数组，用冒泡法进行排序时，共需比较__________次。n(n-1)/2冒泡排序算法4个元素进行冒泡排序时，需要三趟，用i表示趟数i←1i=3?结束Yi←i+1N进行第i趟冒泡排序开始4个元素进行冒泡排序时，需要三趟，用i表示趟数i←1i=3?结束Yi←i+1Nj←4比较a(j)和a(j-1)如果a(j)a(j-1)则交换j←j+1NYj表示元素的位置a(j)与a(j-1)是相邻的元素j=i+1?开始冒泡排序算法8延迟符冒泡排序算法的程序实现冒泡排序程序的实现可用双重For循环来实现，外层For循环控制是第几遍加工，内层For循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进行排序的范围会发生变化(每趟减少一个)，故内层For循环变量的下界由外层循环变量决定。现有n个数据，分别存放在数组变量a(1Ton)当中，用冒泡排序算法表示结构如下：9延迟符冒泡排序算法的基本思想冒泡排序的代码如下(升序)：Fori=1ton-1‘n个数需要n-1次排序Forj=ntoi+1step-1‘从后往前，两两比较，一直到第i+1个数Ifa(j)a(j-1)then‘比较相邻的两个数temp=a(j-1):a(j-1)=a(j):a(j)=temp‘小的在后面，则交换EndIfNextjNexti(注)：从小到大排序，If语句中条件表达式为：a(j)a(j-1)；从大到小排序，If语句中条件表达式为：a(j)a(j-1)。用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。{49,38,65,97,76,13,27,49}分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：对比原数据经过第一趟排序，实现了什么目的？第一趟排序，一共进行了多少次比较？4927137697653849数据87654321序号4938,交换位置原数据和序号序号12345678数据4938659776132749第一趟排序的步骤：序号12345678数据3849659776132749序号12345678数据3849659776132749序号12345678数据3849659776132749序号12345678数据3849657697132749序号12345678数据3849657613972749序号12345678数据3849657613279749序号12345678数据3849657613274997经过第一趟排序，把最大的数沉到最底了！4965,保持不变6597,保持不变9776,交换位置9713,交换位置9727,交换位置9749,交换位置经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了!9749271376654938数据87654321序号3849,保持不变第一趟排序后的数据和序号第二趟排序的步骤：序号12345678数据38496576132749974965,保持不变6576,保持不变7613,交换位置7627,交换位置7649,交换位置序号12345678数据3849657613274997序号12345678数据3849657613274997序号12345678数据3849657613274997序号12345678数据3849651376274997序号12345678数据3849651327764997序号12345678数据38496513274976977697,保持不变序号12345678数据3849651327497697观察原数据与第一、二趟排序后的数据序号12345678数据3849657613274997序号12345678数据3849651327497697序号12345678数据4938659776132749问：为了使这一组无序数组完全按照要求排成从小到大我们还需不需要再继续排序呢？问：那么我们预计最多一共要经过多少次排序呢？序号12345678数据3849132749657697序号12345678数据4938659776132749序号12345678数据3849657613274997序号12345678数据3813274949657697序号12345678数据1327384949657697序号12345678数据3849651327497697序号12345678数据1327384949657697序号12345678数据1327384949657697初始1趟2趟3趟4趟5趟6趟7趟15延迟符冒泡排序算法的基本思想冒泡排序的代码如下(升序)：Fori=1ton-1‘n个数需要n-1次排序Forj=1ton-i‘从前往后，两两比较，一直到第n-i个数Ifa(j)a(j+1)then‘比较相邻的两个数temp=a(j):a(j)=a(j+1):a(j+1)=temp‘小的在后面，则交换EndIfNextjNexti(注)：从小到大排序，If语句中条件表达式为：a(j)a(j+1)；从大到小排序，If语句中条件表达式为：a(j)a(j+1)。1.有以下VB程序段Fori=1To3Forj=iTo5Ifa(j)a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjList1.AddItemStr(a(i))Nextia(1)到a(6)的初始值依次为“865793”，经过该程序段“加工”后，列表框List1中显示的是（）A．876B．879C．653D．567C2.有以下VB程序段Fori=1To2Forj=1To5-iIfa(j+1)a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNexti数据“56,23,78,11,8”依次存放在数组a（1）到a（5）中，执行下列VB程序段后，数组a（1）到a（5）中的数据依次为（）A.8,11,23,56,78B.23,11,8,56,78C.11,8,23,56,78D.8,11,56,23,78B3．有如下VB程序段：Fori=6To4Step-1j=1DoWhilej=i-1Ifa(j)a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfj=j+1LoopNexti数组元素a(1)到a(6)的值依次为“26,13,23,18,7,14”，执行该程序段后，数组元素a(1)到a(6)的值依次为（）A．26,13,23,18,7,14B．13,7,14,18,23,26C．7,13,14,18,23,26D．26,23,18,14,13,7B4.冒泡排序在某一遍加工过程中没有数据交换时，说明数据已经有序，优化程序段如下i=1:flag=TrueDoWhilei=4Andflag=Trueflag=FalseForj=5Toi+1Step-1Ifa(j)a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tflag=TrueEndIfNextji=i+1Loop数组元素a(1)到a(5)的值依次为“48,36,24,97，77”，经过该程序段“加工”后，变量i的值是()A.1B.2C.3D.4D5．有如下程序段：i=1DoWhilei=4Andflag(i)=FalseForj=5Toi+1Step-1Ifa(j)a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag(i)=TrueEndIfNextji=i+1Loop数组元素a(1)到a(5)的值依次为“27，5，25,36,78”，数组flag的初值均为False，经过该程序段“加工”后，数组元素放flag(1)到flag(5)中值为True的个数是()A.1B.2C.3D.4B6.下面程序是一个改进过的冒泡排序：Dima(1To5)AsIntegera(1)=5:a(2)=10:a(3)=9:a(4)=3:a(5)=7n=5:p=0swap=TrueDoWhileswap=Trueswap=FalseFori=1Ton-1Ifa(i)a(i+1)Thent=a(i):a(i)=a(i+1):a(i+1)=tswap=TrueEndIfNextiIfswap=TrueThenp=p+1LoopText1.Text=p该程序段执行后，在文本框Text1中显示的内容为()A.1B.2C.3D.4C7.已知字符串数组a（1）到a（6）的原始数据为”118”，”36”，”98”，”15”，”88”，”2”，为了对该数组进行排序操作，小吴编写了以下VB程序：Fori=1to3Forj=6toi+1step-1Ifa(j)a(j-1)thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti则程序运行之后，数组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”A8.某VB程序段如下：Fori=1To6j=7DoWhilejiIfa(j)a(j-1)Thena(j)=a(j)+a(j-1)a(j-1)=a(j)-a(j–1)a(j)=a(j)-a(j-1)EndIfj=j-1LoopNextiFori=3To6s=s+a(i)NextiLabel1.Caption=Str(s)已知数组元素a(1)到a(7)的值依次为“8,2,3,7,10,6,5”，则执行该程序段后，标签Label1中显示的是()A．21B．26C．41D．18A9.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个数据进行比较。以下程序实现了冒泡排序的优化，在划处填入合适的代码。DimnAsIntegerDima(1To100)AsInteger′n=10，排序前生成的数据存储在数组a中，并在列表框List1中显示代码略PrivateSubCommand1_Click()DimiAsInteger,jAsInteger,startAsInteger,tAsIntegeri=2DoWhilei=nstart=nForj=nToiStep-1If_______________Thent=a(j):a(j)=a(j-1):a(j-1)=t_______________EndIfNextji=start+1LoopFori=1TonList2.