2022選考復(fù)習(xí)系列之一（冒泡排序復(fù)習(xí)）【新教材】浙教版(2019)高中信息技術(shù)選擇性必修一《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》

冒泡排序復(fù)習(xí)浙教版新教材(2019)《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》選擇性必修1——冒泡排序復(fù)習(xí)經(jīng)典冒泡從后往前冒，以下演示從前往后冒2

345101505第一遍：比較5次，交換2次經(jīng)典冒泡從后往前冒，以下演示從前往后冒2

34105第一遍：比較5次，交換2次第二遍：比較4次，交換2次1404經(jīng)典冒泡從后往前冒，以下演示從前往后冒2

3104

5第一遍：比較5次，交換2次第二遍：比較4次，交換2次3130第三遍：比較3次，交換2次經(jīng)典冒泡從后往前冒，以下演示從前往后冒2

103

4

5第一遍：比較5次，交換2次第二遍：比較4次，交換2次第三遍：比較3次，交換2次2120第四遍：比較2次，交換2次經(jīng)典冒泡從后往前冒，以下演示從前往后冒1

02

3

4

5第一遍：比較5次，交換2次第二遍：比較4次，交換2次第三遍：比較3次，交換2次第四遍：比較2次，交換2次10第五遍：比較1次，交換1次經(jīng)典冒泡：從前往后與從后往前，總比較次數(shù)和交換次數(shù)不變，排序遍數(shù)n-1一、冒泡排序思想排序遍數(shù)是？比較次數(shù)？交換次數(shù)？1、2組從前往后冒3、4組從后往前冒一、冒泡排序思想冒泡排序思想總結(jié)：★升序：將后數(shù)小于前數(shù)的兩個(gè)數(shù)進(jìn)行交換；降序：將后數(shù)大于前數(shù)的兩數(shù)進(jìn)行交換★n個(gè)數(shù)最多進(jìn)行

n-1遍排序★兩數(shù)比較的次數(shù)為:n*(n-1)/2★兩數(shù)交換次數(shù)最多為：

n*(n-1)/2升序核心代碼foriinrange(0,n-1):forjinrange(n-1,i,-1)ifa[j]<a[j-1]:

交換a[j]與a[j-1]控制遍數(shù)為n-1遍即可初值定，控制每遍冒泡方向和比較次數(shù)，一般為n-1/n-2或0,1。終值與i和前后項(xiàng)表達(dá)相關(guān)。初值和終值不能換位置。控制次序——后項(xiàng)<前項(xiàng)，交換，升序。表達(dá)方法a[j-1]或a[j+1],從j初值可得二、冒泡排序程序?qū)崿F(xiàn)(一維數(shù)組為例)課堂練習(xí)7.

D三、冒泡排序應(yīng)用觀察d變量，有哪些特征？三、冒泡排序應(yīng)用編程實(shí)現(xiàn)，以左圖形式顯示三、冒泡排序應(yīng)用1編程實(shí)現(xiàn)，按總分高到低排序三、冒泡排序應(yīng)用2編程實(shí)現(xiàn)，女生在前，男生在后，分別按降序排序三、冒泡排序應(yīng)用3編程實(shí)現(xiàn)，男生在前，降序排序，女生在后，升序排序三、冒泡排序應(yīng)用3還有哪些排序形式？出現(xiàn)同分情況怎么處理？只排男生或只排女生？(位置不變）只排前三名不改變?cè)许樞蚺判?？四、冒泡排序?yōu)化1——遍數(shù)優(yōu)化foriinrange(1,len(d)):

flag=False

forjinrange(0,len(d)-i):ifd[j]>d[j+1]:

flag=Trued[j],d[j+1]=d[j+1],d[j]

ifflag==False：

break標(biāo)記是否存在交換變量flag，默認(rèn)無(wú)序有交換，則標(biāo)記True內(nèi)循環(huán)結(jié)束如無(wú)交換，則表明有序一、冒泡排序優(yōu)化1——遍數(shù)優(yōu)化i=1;flag=FalseWhilei<len(d)andflag==False

flag=True

forjinrange(0,len(d)-i):ifd[j]>d[j+1]:

flag=False

d[j],d[j+1]=d[j+1],d[j]

i+=1notflag課堂練習(xí)1.有如下Python程序段：d=[173,172,169,178,183]foriinrange(1,len(d)):c=0forjinrange(0,len(d)-i):ifd[j]>d[j+1]:c+=1

d[j],d[j+1]=d[j+1],d[j]ifc==0:

break則程序運(yùn)行之后，i的值為（）A.1B.2C.3D.4cd=[173,172,169,178,183]foriinrange(1,len(d)):forjinrange(0,len(d)-i):ifd[j]>d[j+1]:c+=1

d[j],d[j+1]=d[j+1],d[j]則程序運(yùn)行之后，c的值為（

）A.10B.8C.5D.3D課堂練習(xí)2.若冒泡排序在某一遍加工過(guò)程中沒(méi)有數(shù)據(jù)交換，則說(shuō)明數(shù)據(jù)已經(jīng)有序，優(yōu)化程序段如下：a=[58,36,23,97,77]n=len(a);i=1;flag=Truewhilei<=4andflag==True:

flag=Flaseforjinrange(4,i-1,-1):ifa[j]>a[j-1]:a[j],a[j-1]=a[j-1],a[j];flag=True

i+=1數(shù)組元素a[0]到a[4]的值依次為“58,36,23,97,77”，經(jīng)過(guò)該程序段“加工”后，變量i的值是___________。4四、冒泡排序優(yōu)化2——范圍優(yōu)化當(dāng)某一遍加工過(guò)程中沒(méi)有數(shù)據(jù)交換，說(shuō)明數(shù)據(jù)已經(jīng)有序，無(wú)需進(jìn)一步加工。當(dāng)某段數(shù)據(jù)某遍加工過(guò)程中未發(fā)生任何一次數(shù)據(jù)交換，說(shuō)明該段數(shù)據(jù)已經(jīng)有序，無(wú)需進(jìn)一步加工，只需處理其后數(shù)據(jù)即可。下次冒泡只需比較到最后記錄的位置，因?yàn)榍岸斡行颉Ｋ?、冒泡排序?yōu)化2——范圍優(yōu)化last=len(d)-1foriinrange(1,len(d)):

c=0

forjinrange(0,last):ifd[j]>d[j+1]:

c+=1;d[j],d[j+1]=d[j+1],d[j]

last=jifc==0:break有如下Python程度段生成隨機(jī)數(shù)組a并將其中的元素從小到大排序：importrandoma=[0]*10;

i=0x=random.randint(1,100)whilei<10：ifxnotina：a[i]=x;i=i+1x=random.randint(1,100)i=0whilei<9：

k=I

;i=9forjinrange(9,k,-1)：ifa[j]<a[j-1]:a[j],a[j-1]=a