第三章算法与程序实现3课件-高中信息技术浙教版必修1

算法与程序设计——方卫龙八、排序算法

排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素(或记录)的任意序列，重新排列成一个关键字有序的序列。排序算法是高考选考的必考内容，考试中主要以冒泡排序算法和选择排序算法为样本进行改编。(1)冒泡排序（升序）Fori=1ton–1Forj=ntoi+1Step-1Ifa(j)<a(j-1)Thent=a(j)a(j)=a(j-1)a(j-1)=tEndifNextjNexti例如：数组元素a(1)到a(6)的值依次为“26、13、23、18、7、14”，执行程序数组元素的变化：i=1i=2j=626132318714j=672613231418j=526132371814j=572613142318j=426137231814j=472613142318j=326713231814j=371326142318j=272613231814i=3i=4j=671326141823j=671314261823j=571326141823j=571314182623j=471314261823i=5j=671314182328

（一）常见变形代码举例aa(1)a(2)a(3)a(4)a(5)a(6)1.VB程序，已知n=6值698351Fori=1ton-1Forj=ntoi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tEndifNextjNexti1234经过____趟后数组就已经有序4169 835136 985135 6981 35689

（一）常见变形代码举例八、排序算法aa(1)a(2)a(3)a(4)a(5)a(6)2.VB程序，已知n=6值658139Fori=1ton-1Forj=iton-iIfa(j)<a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjNexti12345经过____趟后数组就已经有序56853918659318695318965319865311.有以下VB程序段ForI=1to3Forj=1to5Ifa(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.5672.有以下VB程序段Fori=1to2Forj=1to5–iIfa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjNextI数据“562378118”依次存放在数组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,783.有以下VB程序段Fori=1to2Forj=1to5–iIfa(j)>a(j+1)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndifNextjNexti数组元素a(1)到a(5)值依次为“24,20,45,16,18”,经过该程序段“加工”后，数组元素a(1)到a(5)的依次为（）A.1618202445B.2016182445C.1618242045D.45242018164.有以下VB程序段ForI=6to4step-1j=1DoWhilej<=i-1Ifa(j)>a(j+1)Then

t=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,7八、排序算法之冒泡CBBB5.冒泡排序在某一遍加工过程中没有数据交换时，说明数据已经有序，优化程序段如下I=1:flag=TrueDoWhilei<=4andflag=Trueflag=FalseForj=5toI+1Step-1Ifa(j)>a(j-1)Then

t=a(j):a(j)=a(j-1):a(j-1)=tflag=TrueEndifNextji=i+1Loop数组元素a(1)到a(5)的值依次为“48,36,24,97,77”,经过该程序段“加工”后，变量i的值是（）1B.2C.3D.46.有以下VB程序段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.47.下面程序是一个改进过后冒泡排序：Dima(1to5)asintegera(1)=5:a(2)=10:a(3)=9:a(4)=3:a(5)=7n=5:p=0:swap=TrueDoWhileswap=Trueswap=FalseFori=1ton-1Ifa(i)>a(i+1)Then

t=a(j):a(j)=a(j+1):a(j+1)=tswap=TrueEndifNextIIfswap=TrueThenp=p+1LoopText1.Text=p该程序段执行后，在文本框Text1中显示的内容为：（）A.1B.2C.3D.48.以下程序段对数组a中的6个数据a(1)到a(6)进行加工。DimflagasBooleani=1:flag=TrueDoWhilei<=5andflag=Trueflag=FalseForj=6Toi+1Step-1Ifa(j)<a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEndifNextji=i+1Loop下列数组序列中，在加工过程中划线处语句执行次数最多的是()A.24,29,31,20,15,10

B.10,15,20,24,29,31C.29,10,31,15,20,24D.31,29,24,20,15,10八、排序算法之冒泡DBCD1.n个数据的冒泡升序排序需要经过n-1遍的加工，每一遍加工自下而上比较相邻两个数据，把较小者交换到上面，在第i遍加工过程中需要进行对数据的比较。在某些情况下，第遍加工过程中，在上面部分较小数据已经有序情况下，不需要再进行对数据的比较。如对“17，18，19，24，23，20”这6个数据排序中，第1遍排序结束数据为“17，18，19，20，24，23”，第2遍排序时不再需要对20及其前面4个数据进行比较。以下程序实现了冒泡排序的优化，在划线处填入合适代码。Dimnasinteger,a(1to100)asintegerPrivateSubCommand1_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.additem_________NextiEndSub八、排序算法之冒泡a(j)<a(j-1)start=jStr(a(i))2.小华在探究将两段已按从小到大排序的数据连接后用冒泡排序思想再进行从小到大排序的情况，编写VB程序功能如下：在列表框List1中显示排序前数据（存储在数组c中）,单击“排序”按钮Command1后，在列表框List2中显示排序后的数据。程序运行界面如图所示。实现上述功能的VB程序如下，在划线处填入合适的代码。Constn1=6‘第1段已排序数据长度为n1Constn2=5‘第2段已排序数据长度为n2Dimc(1ton1+n2)asinteger‘数组C长度为n1+n2，依次存储第1、2段数据PrivateSubCommand1_Click()‘数组c依次存储两段已按从小到大排序的数据，并在列表框List1中显示，代码略。Fori=n1+1ton1+n2j=1Flag=TrueDoWhile_____________Ifc(j)<c(j-1)Thent=c(j):c(j)=c(j-1):c(j-1)=tElseFlag=FalseEndif________________LoopNextiFori=1to____________List2.additemc(i)NextiEndSub八、排序算法之冒泡j>1andFlagj=j-1n1+n23.小王设计一个计算比赛得分的VB程序，程序功能如下：依次在文本框Text1中输入某选手的评委打分，按回车键后显示在列表框List1中，点击“统计”按钮Command1,在标签Label3中输出该选手的平均得分。平均得分的计算方法如下：若有n位评委为选手打分，则该选手的平均得分是从这n位评委打分中去掉一个最高分和一个最低分后的平均分。程序运行界面如图所示。加框处代码有错,请改正.

Dimd(1to20)assingle,nasinteger‘数组d存放评委（≤20人）打分数据，n存放评委人数PrivateSubText1_KeyPress(KeyAsciiasinteger)‘在文本框Text1中输入评委打分，并存入数组d，统计评委人数保存在变量中，代码略EndSubPrivateSubComman1_Click()DimtempasSingle,sassingle,averassingle,iasinteger,jasintegers=0Fori=n-1To1Step-1Forj=1toiIfd(j)<d(j+1)Thentemp=d(j)d(j)=d(j+1)temp=d(j+1)EndifNextjIfi<>n-1Thens=d(i)Nextiaver=Int(s/(n-2)*100+0.5)/100Label3.Caption=Str(aver)EndSub八、排序算法之冒泡d(j+1)=temps+d(i+1)4.冒泡算法，当数据已经有序时就停止加工，为此编写了一个VB程序，功能如下：运行程序时，在列表框List1中显示排序前数据，单击“排序”按钮Command1,在列表框List2中显示按升序排序后的结果，在标签Label1中显示排序加工趟数、在标签Label2中显示数据变换次数。运行效果如图所示。实现上述功能的VB代码如下，但加框处代码有错，请改正。Constn=10Dima(1ton)asinteger‘排序前数据储在数组a中，并在Label1中显示，代码略PrivateSubCommand1_Click()DimflagasBoolean,xasinteger,yasintegerx=0:y=0:flag=True:i=1DoWhilei<=n-1andflagflag=FalseForj=ntoi+1Step-1Ifa(j)<>a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tflag=Truex=1EndIfNextjy=y+1i=n–1LoopLabel1.Caption=“经过”+Str(y)+“趟排序数据有序！”Label2.Caption=“数据总共交互”+Str(x)+“次！”Fori=1tonList2.additemStr(a(i))NextiEndSub八、排序算法之冒泡a(j)<a(j-1)x=x+1i=i+15.小刘在研究n个数的冒泡排序算法，发现可以从两个方面行优化：（1）在每遍冒泡过程中，若最后一次交的是last与last-1位置的，last位置之前的相邻据均已有序。进行下一遍冒泡，无序区域设置[last,n]，一遍排序可能使当前无序区域缩小。（2）若在某一遍排序中没有数据交换，说明待排序数据都已经有序，冒泡排序程序可在此遍排序后结束。因此可以引入一个变量flag，记录在每遍排序过程中是否发生了交换。小刘上述方法的冒泡优化VB程序，功能如下：“生成数据”按Command1后，生成一组随机的两位整数存入数组a,并显示在列表框Last1中。单击“排序”按Command2后，a中的数据进行降序排序,排序后的数据显示在列表框Last2中排序过程中实际的冒泡遍数显示在Label2。程序运行界面如图所示。(1)若优化后的冒泡排序算法，数据28,15,10,8,12进行降序排序，冒泡的遍数________.(2)在划线填入合适的代码。Dima(1to20)asintegerPrivateSubCommand1_Click()DimIasinteger,jasintegerList1.Clear:List2.ClearRandomizeFori=1to20______________Forj=1toi-1Ifa(i)=a(j)Theni=i-1:ExitForNextjNextIFori=1to20List1.additemStr(a(i))NextIEndSub八、排序算法之冒泡PrivateSubCommand2_Click()DimflagasBoolean,iasinteger,jasintegerDimtempasInteger,numasInteger,lastasIntegernum=0:last=1Flag=TrueDoWhileflag=True______________Forj=20tolast+1Step-1Ifa(j)>a(j-1)Thentemp=a(j):a(j)=a(j-1):a(j-1)=temp__________________flag=True‘有交换发生EndifNextjnum=num+1LoopForI=1to20List2.additemStr(a(i))NextILabel3.Caption=“本次排序的冒泡遍数为：”﹠Str(num)EndSub2a(i)=Int(Rnd*90)+10flag=Falselast=j6.小李编写“合并区间”VB程序，功能如下:窗体加载时，获取并存储合并前的区间的数据，并显示在列表框List1中。单击“合并”按钮后,

以区间左端点数值对区间进行升序排序，然后相邻区间的相交进行合并，最后在列表框List2上显示合并后的区间.程序运行如图所示：实现以上功能的VB程序如下，在划线处填入合适的代码。Dima(1to20)asinteger,b(1to20)asinteger‘数组a、b分别存储区间的左端点、右端点数值PrivateSubForm_Load()‘将区间左端点存入a，区间右端点存入数组b，并在列表框List1显示，代码略EndSubPrivateSubCommand1_Click()Dimiasinteger,jasintegerDimcurLasinteger,curRasintegerFori=1ton-1Forj=1ton-IIf________________Thent=a(j):a(j)=a(j+1):a(j+1)=tt=b(j):b(j)=b(j+1):b(j+1)=tEndif____________NexticurL=a(1):curR=b(1)ForI=2tonIfa(i)<=curRThenIfcurR<b(i)Then_____________ElseList2.Additem“[”+Str(curL)+Str(curR)+“]”curL=a(i):curR=b(i)EndIfNextiList2.Additem“[”+Str(curL)+Str(curR)+“]”EndSub

八、排序算法之冒泡a(j)>a(j+1)NextjcurR=b(i)7.活动课上，n个学生要两两组队进行拔河比赛，要求每个小组总体重不超过120KG，小林想知道最多可以组成多少个队伍，并希望得到可以的组队方案。于是设计了如下界面的程序，在文本框Text1中输入n个学生的体重（数字之间用逗号隔开），单击“队伍”按钮Command1后在标签Label1上显示最多可能组队数量，同时在列表框List1输出方案。实现上述功能程序如下，在划线处填入合适代码.Dimnasinteg