排序算法及程序?qū)崿F(xiàn)課件1

排序算法及程序?qū)崿F(xiàn)（1）排序算法及程序?qū)崿F(xiàn)（1）2教材研讀一

排序算法的基本思想二

排序算法的程序?qū)崿F(xiàn)2教材研讀一 排序算法的基本思想二 排序算法的程序?qū)崿F(xiàn)3重難突破突破

冒泡排序的變形3重難突破突破冒泡排序的變形4教材研讀4教材研讀知識(shí)梳理一、排序算法的基本思想通常被排序的數(shù)據(jù)是一批同類型數(shù)據(jù),存儲(chǔ)在具有適當(dāng)規(guī)模的數(shù)組變量中。通過排序可以調(diào)整數(shù)據(jù)在數(shù)組變量中的存儲(chǔ)位置,使數(shù)組內(nèi)的數(shù)據(jù)呈現(xiàn)某種次序。5知識(shí)梳理一、排序算法的基本思想5知識(shí)梳理(1)冒泡排序冒泡排序的基本思想是把待排序的n個(gè)元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù),從最下面的一個(gè)數(shù)據(jù)起,自下而上地比較相鄰的兩個(gè)數(shù)據(jù),將較小的數(shù)據(jù)換到上面。重復(fù)這一過程,直到處理完最后兩個(gè)數(shù)據(jù),稱為一遍加工。第一遍加工完成后,最小的數(shù)據(jù)已經(jīng)上升到第1個(gè)位置。然后對(duì)余下的n-1個(gè)數(shù)據(jù)重復(fù)上述處理過程,這是第二遍加工,第二遍加工完成后,第二小的數(shù)據(jù)上升到了第2個(gè)位置。然后再對(duì)余下的n-2個(gè)元素進(jìn)行加工……。n個(gè)數(shù)需要n-1次加工。6知識(shí)梳理(1)冒泡排序6知識(shí)梳理以數(shù)據(jù)130,20,98,15,67,3為例,從小到大冒泡排序的過程如下:7原始數(shù)據(jù)130209815673第1遍排序后313020981567第2遍排序后315130209867第3遍排序后315201306798第4遍排序后315206713098第5遍排序后315206798130知識(shí)梳理以數(shù)據(jù)130,20,98,15,67,3為例,從小知識(shí)梳理二、排序算法的程序?qū)崿F(xiàn)(1)冒泡排序的代碼如下:8Fori=1Ton-1

n個(gè)數(shù)需要n-1次排序Forj=nToi+1Step-1

從后往前,兩兩比較,一直到第i+1個(gè)數(shù)Ifa(j)<a(j-1)Then

比較相鄰的兩個(gè)數(shù)temp=a(j-1):a(j-1)=a(j):a(j)=temp

小的在后面,則交換EndIfNextjNexti知識(shí)梳理二、排序算法的程序?qū)崿F(xiàn)8Fori=1Ton-1知識(shí)梳理從小到大排序,If語句中條件表達(dá)式為:a(j)<a(j-1);從大到小排序,If語句中條件表達(dá)式為:a(j)>a(j-1)。9知識(shí)梳理從小到大排序,If語句中條件表達(dá)式為:a(j)<a(自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12,2分)對(duì)下列數(shù)據(jù)序列進(jìn)行冒泡升序排序,在排序過程中效率最低的序列是

(

)A.31,29,24,20,15,10B.10,15,20,24,29,31C.29,10,31,15,20,24D.24,29,31,20,15,1010自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12,2分)對(duì)下列數(shù)據(jù)序列進(jìn)行冒泡升序排序,在排序過程中效率最低的序列是

(A)A.31,29,24,20,15,10B.10,15,20,24,29,31C.29,10,31,15,20,24D.24,29,31,20,15,1011自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12自我檢測解析

本題考查冒泡排序的基本原理。在比較次數(shù)一定的情況下,冒泡排序的效率與數(shù)據(jù)發(fā)生的交換次數(shù)有關(guān)。選項(xiàng)A中的數(shù)據(jù)是逆序(降序)排列,因此實(shí)現(xiàn)升序排序需要交換的次數(shù)最多,效率最低。12自我檢測解析本題考查冒泡排序的基本原理。在比較次數(shù)一定的情自我檢測2.有如下程序段:Fori=1To2Forj=5Toi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti數(shù)組元素a(1)到a(5)的值依次為“95,88,66,80,75”,經(jīng)過該程序段“加

工”后,數(shù)組元素a(1)到a(5)的值依次為

(

)A.66,75,95,88,80B.66,75,80,95,88C.95,88,66,80,75D.95,88,80,75,6613自我檢測2.有如下程序段:13自我檢測2.有如下程序段:Fori=1To2Forj=5Toi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti數(shù)組元素a(1)到a(5)的值依次為“95,88,66,80,75”,經(jīng)過該程序段“加

工”后,數(shù)組元素a(1)到a(5)的值依次為

(

A

)A.66,75,95,88,80B.66,75,80,95,88C.95,88,66,80,75D.95,88,80,75,6614自我檢測2.有如下程序段:14自我檢測解析

此題為冒泡排序變形題,升序排序,排序兩趟。答案為A。15自我檢測解析此題為冒泡排序變形題,升序排序,排序兩趟。答案16重難突破16重難突破突破冒泡排序的變形1.冒泡排序的標(biāo)準(zhǔn)寫法(升序):Fori=1Ton-1

n個(gè)數(shù)需要n-1次排序Forj=nToi+1Step-1

從后往前,兩兩比較,一直到第i+1個(gè)數(shù)Ifa(j)<a(j-1)Then

比較相鄰的兩個(gè)數(shù)temp=a(j-1):a(j-1)=a(j):a(j)=temp

小的在后面,則交換EndIfNextjNexti17突破冒泡排序的變形1.冒泡排序的標(biāo)準(zhǔn)寫法(升序):17突破冒泡排序的變形排序思想解析:n個(gè)數(shù)需要n-1遍排序;每一遍排序中,都是從最后一個(gè)數(shù)開始,兩兩比較,小的換到前面,大的換到后面;第一遍把最小數(shù)推到了第一個(gè)位置,第二遍把第二小的數(shù)推到了第二個(gè)位置,……。因此排序過程中,是前面的數(shù)據(jù)先排好。18突破冒泡排序的變形排序思想解析:n個(gè)數(shù)需要n-1遍排序;每突破冒泡排序的變形2.冒泡排序的變形一(升序)Fori=1Ton-1Forj=nToi+1Step-1Ifa(j)<a(j-1)Thentemp=a(j-1):a(j-1)=a(j):a(j)=tempEndIfNextjNexti19突破冒泡排序的變形2.冒泡排序的變形一(升序)19突破冒泡排序的變形排序思想解析:與標(biāo)準(zhǔn)式唯一的差異就是兩個(gè)比較項(xiàng)從a(j-1)和a(j)變成a(j+1)和a(j),因此循環(huán)語句也從“Forj=nToi+1Step-1”變成了

“Forj=n-1ToiStep-1”,本質(zhì)上排序過程,與標(biāo)準(zhǔn)式是完全一樣的。20突破冒泡排序的變形排序思想解析:與標(biāo)準(zhǔn)式唯一的差異就是兩個(gè)突破冒泡排序的變形3.冒泡排序的變形二(升序)Fori=1Ton-1Forj=1Ton-iIfa(j+1)<a(j)Thentemp=a(j+1):a(j+1)=a(j):a(j)=tempEndIfNextjNexti21突破冒泡排序的變形3.冒泡排序的變形二(升序)21突破冒泡排序的變形排序思想解析:跟標(biāo)準(zhǔn)型不一樣的是本代碼中每一遍冒泡是從前往后兩兩比較的,因此每一遍排序達(dá)到的效果是把最大值推到了最后面。第一遍排序后,最大值就到了最后位置,第二遍后,次大值就到了倒數(shù)第二個(gè)位置……。排序過程中,是后面的數(shù)據(jù)先排好,因此每一遍排序的初值都是1,后面的數(shù)隨著一遍遍的排序慢慢排好了,因此終值是變化的,為n-i。22突破冒泡排序的變形排序思想解析:跟標(biāo)準(zhǔn)型不一樣的是本代碼中突破冒泡排序的變形4.冒泡排序的變形三(升序)Fori=1Ton-1Forj=i+1TonIfa(j)<a(i)Thentemp=a(j):a(j)=a(i):a(i)=tempEndIfNextjNexti23突破冒泡排序的變形4.冒泡排序的變形三(升序)23突破冒泡排序的變形排序思想解析:在第i遍的排序中,把第i+1到第n個(gè)數(shù)依次與a(i)比較,如果比a(i)小,則交換。它的最大特點(diǎn)是:永遠(yuǎn)跟一個(gè)固定位置上的數(shù)去比較。排序過程中,是前面的數(shù)據(jù)先排好。24突破冒泡排序的變形排序思想解析:在第i遍的排序中,把第i+突破冒泡排序的變形5.冒泡排序的錯(cuò)誤變形Fori=1Ton-1Forj=iTon-1Ifa(j+1)<a(j)Thentemp=a(j+1):a(j+1)=a(j):a(j)=tempEndIfNextjNexti25突破冒泡排序的變形5.冒泡排序的錯(cuò)誤變形25突破冒泡排序的變形錯(cuò)誤原因解析:從語句“Forj=iTon-1”可看出每一遍的冒泡過程是把最大值從前往后推,因此排序過程中,是后面的數(shù)據(jù)先排好,前面的數(shù)據(jù)是亂的,但是第i遍的冒泡過程是從第i個(gè)數(shù)開始的,因此i位置前面的數(shù)據(jù)不能參與排序。而后面的數(shù)據(jù)已經(jīng)排好的,其實(shí)是不需要參與排序的。因此要改成“Forj=1Ton-i”26突破冒泡排序的變形錯(cuò)誤原因解析:從語句“Forj=iT突破冒泡排序的變形6.冒泡排序的優(yōu)化當(dāng)某一遍排序過程中沒有數(shù)據(jù)交換,說明數(shù)據(jù)已經(jīng)有序,無需進(jìn)行下一遍排序。代碼如下:DimflagAsBooleani=1flag=True

flag值為True表示一遍加工中發(fā)生過交換DoWhilei<=n-1Orflag=trueflag=False27突破冒泡排序的變形6.冒泡排序的優(yōu)化27突破冒泡排序的變形Forj=nToi+1Step-1Ifa(j)<a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEndIfNextji=i+1Loop28突破冒泡排序的變形Forj=nToi+1Step突破冒泡排序的變形思想解析:用一個(gè)邏輯變量flag標(biāo)記某一遍排序過程中是否有數(shù)據(jù)交換,如果沒有,則無需再進(jìn)行下一遍排序。排序遍數(shù)是i-1遍。另一種寫法:DimflagAsBooleanFori=1ton-1flag=falseForj=nToi+1Step-1Ifa(j)<a(j-1)Then29突破冒泡排序的變形思想解析:用一個(gè)邏輯變量flag標(biāo)記某一突破冒泡排序的變形k=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEndIfNextjIfflag=falsethenexitforNexti注意:這種寫法的排序遍數(shù)是i次,因?yàn)槌绦驈闹虚g跳出循環(huán),不執(zhí)行“nexti”指令,因此沒有多加一次。30突破冒泡排序的變形k=a(j):a(j)=a(j-1典題精練例1對(duì)于a數(shù)組排序的程序段如下:Fori=1Ton-1Forj=nToi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-l)=tEndIfNextjNexti31典題精練例1對(duì)于a數(shù)組排序的程序段如下:31典題精練則下列程序段運(yùn)行后,a數(shù)組的排序情況與上面程序段運(yùn)行結(jié)果不同的是(D)32Fori=1Ton-1Forj=1Ton-iIfa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNextiFori=1Ton-1Forj=i+1TonIfa(i)>a(j)Thent=a(i):a(i)=a(j):a(j)=tEndIfNextjNextiAB典題精練則下列程序段運(yùn)行后,a數(shù)組的排序情況與上面程序段運(yùn)行典題精練33Fori=1Ton-1Forj=n-1ToiStep-1Ifa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNextiFori=1Ton-1Forj=iTon-1Ifa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNextiCD典題精練33Fori=1Ton-1Fori=1To典題精練解析

題干中的程序是冒泡排序,從后往前,小的元素上冒,最終實(shí)現(xiàn)升序排序。A選項(xiàng)是從前往后,大的元素下沉,實(shí)現(xiàn)升序排序。B選項(xiàng),程序第i趟加工即將第i個(gè)數(shù)據(jù)和后面的每個(gè)數(shù)據(jù)比較一遍,使得第i個(gè)數(shù)據(jù)比它后面的每個(gè)數(shù)據(jù)都小,所以也是升序。C選項(xiàng)和題干一樣,只是變化了一下循環(huán)變量的表示方式。D選項(xiàng)是從前往后比,大的元素下沉,但是它除了第一趟把所有的數(shù)據(jù)比較了一遍,從第二趟開始,比較的位置就發(fā)生了錯(cuò)誤,前面的數(shù)據(jù)沒有比較。所以答案選D。34典題精練解析題干中的程序是冒泡排序,從后往前,小的元素上冒典題精練例2冒泡排序在某一遍加工過程中沒有數(shù)據(jù)交換時(shí),說明數(shù)據(jù)己經(jīng)有

序,優(yōu)化程序段如下:i=1:flag=TrueDoWhilei<=4Andflag=Trueflag=FalseForj=5Toi+1Step-1Ifa(j)>a(j-1)Thent=a(j):a(j)=a(j-l):a(j-l)=t35典題精練例2冒泡排序在某一遍加工過程中沒有數(shù)據(jù)交換時(shí),說明典題精練flag=TrueEndIfNextji=i+1Loop數(shù)組元素a(l)到a(5)的值依次為“48,36,24,97,77”,經(jīng)過該程序段“加

工”后,變量i的值是

(

)A.1B.2C.3D.436典題精練flag=True36典題精練flag=TrueEndIfNextji=i+1Loop數(shù)組元素a(l)到a(5)的值依次為“48,36,24,97,77”,經(jīng)過該程序段“加

工”后,變量i的值是

(D)A.1B.2C.3D.437典題精練flag=True37典題精練解析

本題解題的關(guān)鍵在于理解變量flag的作用。邏輯類型變量flag用于標(biāo)記排序過程中數(shù)據(jù)是否有過交換,如果有交換,值為True否則為False。變量i為排序的趟數(shù),從內(nèi)循環(huán)看是降序排序,從后往前,大的元素上冒,因此經(jīng)過兩趟排序后數(shù)組a中的元素有序,第三趟時(shí)i初始值為3,數(shù)據(jù)沒有交換,但再一次執(zhí)行了i=i+1這一語句,所以i=4,當(dāng)i=4時(shí),由于前一趟數(shù)據(jù)沒有交換,flag=False,結(jié)束循環(huán)。所以答案選D。38典題精練解析本題解題的關(guān)鍵在于理解變量flag的作用。39真題在線39真題在線真題在線1.(2017浙江11月選考,16,3分)小李基于冒泡排序算法編寫了一個(gè)VB程序,功能如下:在文本框Text1中顯示排序前的數(shù)據(jù),單擊“排序”按鈕Command1,在文本框Text2中顯示剔除重復(fù)數(shù)據(jù)后的升序排序結(jié)果。程序運(yùn)行界面如圖所示。40真題在線1.(2017浙江11月選考,16,3分)小李基于冒真題在線實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正。Constn=10Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,tAsIntegerDimbottomAsInteger剔除重復(fù)數(shù)據(jù)后元素的個(gè)數(shù)’獲取排序前數(shù)據(jù)依次存儲(chǔ)在數(shù)組a中,并在文本框Text1中顯示。代碼略41真題在線實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正真題在線bottom=ni=1DoWhilei<=bottom-1Forj=bottomToi+1Step-1Ifa(j)<a(i)Then(1)t=a(j):a(j)=a(j-1):a(j-1)=tElseIfa(j)=a(j-1)Then若相鄰兩個(gè)數(shù)據(jù)相等,進(jìn)行剔除處理42真題在線bottom=n42真題在線

a(bottom)=a(j)(2)bottom=bottom-1EndIfNextji=i+1Loop43真題在線 a(bottom)=a(j)(2)43真題在線Text2.Text=“”Fori=1TobottomText2.Text=Text2.Text+Str(a(i))NextiEndSub44真題在線Text2.Text=“”44真題在線答案(1)a(j)<a(j-1)(或a(j-1)>a(j)或其他等價(jià)表達(dá)式)(2)a(j)=a(bottom)(或其他等價(jià)語句)45真題在線答案(1)a(j)<a(j-1)(或a(j-1)>真題在線解析

(1)本程序使用冒泡排序思想,從小到大升序排序(后面元素比前面元素小要交換)。根據(jù)以下交換數(shù)據(jù)的代碼可以推斷,比較的是a(j)和a(j-1)的值。(2)如果a(j)=a(j-1),則表示a(j)和a(j-1)重復(fù)了,可以丟棄其中一個(gè),可將數(shù)組最后一個(gè)值即a(bottom)放到a(j)的位置上替代a(j),然后bottom的值減1,相當(dāng)于數(shù)組規(guī)模減少1個(gè)。46真題在線解析(1)本程序使用冒泡排序思想,從小到大升序排序真題在線2.(2016浙江10月學(xué)考+選考,16,3分)小吳為了探究冒泡排序過程中數(shù)據(jù)的“移動(dòng)”情況,編寫了一個(gè)VB程序,功能如下:在列表框List1中顯示排序前數(shù)據(jù)(存儲(chǔ)在數(shù)組a中),在文本框Text1中輸入初始位置(即下標(biāo)值),單擊“排序”按鈕Command1后,在標(biāo)簽Label1中顯示指定初始位置的數(shù)據(jù)在排序過程中的位置變化情況,排序后的數(shù)據(jù)顯示在列表框List2中,程序運(yùn)行界面如圖所示。47真題在線2.(2016浙江10月學(xué)考+選考,16,3分)小吳真題在線實(shí)現(xiàn)上述功能的VB程序如下,但加框處代碼有錯(cuò),請(qǐng)改正。Dima(1To8)AsIntegerDimnAsIntegerPrivateSubForm_Load()’n=8,排序前的8個(gè)數(shù)據(jù)存儲(chǔ)在數(shù)組a中,并在列表框List1中顯示’代碼略EndSub48真題在線實(shí)現(xiàn)上述功能的VB程序如下,但加框處代碼有錯(cuò),請(qǐng)改正真題在線PrivateSubCommand1_Click()DimiAsInteger,jAsInteger,kAsIntegerDimposAsInteger’變量pos存儲(chǔ)指定數(shù)據(jù)的位置(即下標(biāo)值)DimsAsString ’變量s存儲(chǔ)pos變化情況s=Text1.Textpos=Val(Text1.text)49真題在線PrivateSubCommand1_Click真題在線Fori=1Ton-1Forj=nToi+1Step-1Ifa(j)<a(j-1)Then

k=a(j)(1)a(j-1)=a(j)a(j)=k’如果pos位置的數(shù)據(jù)參與交換,則更新pos值,記錄pos變化情況

Ifpos=jThenpos=j-150真題在線Fori=1Ton-150真題在線s=s+“→”+Str(pos)

Else’(2)pos=js=s+“→”+Str(pos)EndIfEndIfNextjNexti51真題在線s=s+“→”+Str(pos)51真題在線Labell.Caption=“位置變化情況:”+sFori=1TonList2.AddItemStr(a(i))NextiEndSub52真題在線Labell.Caption=“位置變化情況:”+s真題在線答案(1)k=a(j-1)(2)ElseIfpos=j-1Then(其中pos=j-1可用其他等價(jià)表達(dá)式)53真題在線答案(1)k=a(j-1)53真題在線解析

本題主要考查冒泡排序算法的程序?qū)崿F(xiàn)。(1)本小題考查如何實(shí)現(xiàn)兩個(gè)數(shù)的交換。冒泡排序需要比較相鄰兩個(gè)數(shù)的大小,若后一個(gè)數(shù)比前一個(gè)數(shù)小,則交換兩個(gè)數(shù)的位置。此處代碼應(yīng)該是k=a(j-1),即先將a(j-1)的值存入臨時(shí)變量k,再將a(j)的值賦值給a(j-1),最后將臨時(shí)變量k的值賦值給a(j)。(2)本小題考查塊if語句的運(yùn)用。當(dāng)兩個(gè)相鄰的數(shù)a(j)與a(j-1)有位置交換時(shí),需要更新pos的值。若pos值為j時(shí),更新pos值為j-1;若pos值為j-1時(shí),更新pos值為j。54真題在線解析本題主要考查冒泡排序算法的程序?qū)崿F(xiàn)。54課堂總結(jié)教材研讀重難突破一

排序算法的基本思想二

排序算法的程序?qū)崿F(xiàn)突破

冒泡排序的變形課堂總結(jié)教材研讀重難突破一 排序算法的基本思想二 排序算法的排序算法及程序?qū)崿F(xiàn)（1）排序算法及程序?qū)崿F(xiàn)（1）57教材研讀一

排序算法的基本思想二

排序算法的程序?qū)崿F(xiàn)2教材研讀一 排序算法的基本思想二 排序算法的程序?qū)崿F(xiàn)58重難突破突破

冒泡排序的變形3重難突破突破冒泡排序的變形59教材研讀4教材研讀知識(shí)梳理一、排序算法的基本思想通常被排序的數(shù)據(jù)是一批同類型數(shù)據(jù),存儲(chǔ)在具有適當(dāng)規(guī)模的數(shù)組變量中。通過排序可以調(diào)整數(shù)據(jù)在數(shù)組變量中的存儲(chǔ)位置,使數(shù)組內(nèi)的數(shù)據(jù)呈現(xiàn)某種次序。60知識(shí)梳理一、排序算法的基本思想5知識(shí)梳理(1)冒泡排序冒泡排序的基本思想是把待排序的n個(gè)元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù),從最下面的一個(gè)數(shù)據(jù)起,自下而上地比較相鄰的兩個(gè)數(shù)據(jù),將較小的數(shù)據(jù)換到上面。重復(fù)這一過程,直到處理完最后兩個(gè)數(shù)據(jù),稱為一遍加工。第一遍加工完成后,最小的數(shù)據(jù)已經(jīng)上升到第1個(gè)位置。然后對(duì)余下的n-1個(gè)數(shù)據(jù)重復(fù)上述處理過程,這是第二遍加工,第二遍加工完成后,第二小的數(shù)據(jù)上升到了第2個(gè)位置。然后再對(duì)余下的n-2個(gè)元素進(jìn)行加工……。n個(gè)數(shù)需要n-1次加工。61知識(shí)梳理(1)冒泡排序6知識(shí)梳理以數(shù)據(jù)130,20,98,15,67,3為例,從小到大冒泡排序的過程如下:62原始數(shù)據(jù)130209815673第1遍排序后313020981567第2遍排序后315130209867第3遍排序后315201306798第4遍排序后315206713098第5遍排序后315206798130知識(shí)梳理以數(shù)據(jù)130,20,98,15,67,3為例,從小知識(shí)梳理二、排序算法的程序?qū)崿F(xiàn)(1)冒泡排序的代碼如下:63Fori=1Ton-1

n個(gè)數(shù)需要n-1次排序Forj=nToi+1Step-1

從后往前,兩兩比較,一直到第i+1個(gè)數(shù)Ifa(j)<a(j-1)Then

比較相鄰的兩個(gè)數(shù)temp=a(j-1):a(j-1)=a(j):a(j)=temp

小的在后面,則交換EndIfNextjNexti知識(shí)梳理二、排序算法的程序?qū)崿F(xiàn)8Fori=1Ton-1知識(shí)梳理從小到大排序,If語句中條件表達(dá)式為:a(j)<a(j-1);從大到小排序,If語句中條件表達(dá)式為:a(j)>a(j-1)。64知識(shí)梳理從小到大排序,If語句中條件表達(dá)式為:a(j)<a(自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12,2分)對(duì)下列數(shù)據(jù)序列進(jìn)行冒泡升序排序,在排序過程中效率最低的序列是

(

)A.31,29,24,20,15,10B.10,15,20,24,29,31C.29,10,31,15,20,24D.24,29,31,20,15,1065自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12,2分)對(duì)下列數(shù)據(jù)序列進(jìn)行冒泡升序排序,在排序過程中效率最低的序列是

(A)A.31,29,24,20,15,10B.10,15,20,24,29,31C.29,10,31,15,20,24D.24,29,31,20,15,1066自我檢測1.(2016浙江名校新高考研究聯(lián)盟第一次聯(lián)考,12自我檢測解析

本題考查冒泡排序的基本原理。在比較次數(shù)一定的情況下,冒泡排序的效率與數(shù)據(jù)發(fā)生的交換次數(shù)有關(guān)。選項(xiàng)A中的數(shù)據(jù)是逆序(降序)排列,因此實(shí)現(xiàn)升序排序需要交換的次數(shù)最多,效率最低。67自我檢測解析本題考查冒泡排序的基本原理。在比較次數(shù)一定的情自我檢測2.有如下程序段:Fori=1To2Forj=5Toi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti數(shù)組元素a(1)到a(5)的值依次為“95,88,66,80,75”,經(jīng)過該程序段“加

工”后,數(shù)組元素a(1)到a(5)的值依次為

(

)A.66,75,95,88,80B.66,75,80,95,88C.95,88,66,80,75D.95,88,80,75,6668自我檢測2.有如下程序段:13自我檢測2.有如下程序段:Fori=1To2Forj=5Toi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti數(shù)組元素a(1)到a(5)的值依次為“95,88,66,80,75”,經(jīng)過該程序段“加

工”后,數(shù)組元素a(1)到a(5)的值依次為

(

A

)A.66,75,95,88,80B.66,75,80,95,88C.95,88,66,80,75D.95,88,80,75,6669自我檢測2.有如下程序段:14自我檢測解析

此題為冒泡排序變形題,升序排序,排序兩趟。答案為A。70自我檢測解析此題為冒泡排序變形題,升序排序,排序兩趟。答案71重難突破16重難突破突破冒泡排序的變形1.冒泡排序的標(biāo)準(zhǔn)寫法(升序):Fori=1Ton-1

n個(gè)數(shù)需要n-1次排序Forj=nToi+1Step-1

從后往前,兩兩比較,一直到第i+1個(gè)數(shù)Ifa(j)<a(j-1)Then

比較相鄰的兩個(gè)數(shù)temp=a(j-1):a(j-1)=a(j):a(j)=temp

小的在后面,則交換EndIfNextjNexti72突破冒泡排序的變形1.冒泡排序的標(biāo)準(zhǔn)寫法(升序):17突破冒泡排序的變形排序思想解析:n個(gè)數(shù)需要n-1遍排序;每一遍排序中,都是從最后一個(gè)數(shù)開始,兩兩比較,小的換到前面,大的換到后面;第一遍把最小數(shù)推到了第一個(gè)位置,第二遍把第二小的數(shù)推到了第二個(gè)位置,……。因此排序過程中,是前面的數(shù)據(jù)先排好。73突破冒泡排序的變形排序思想解析:n個(gè)數(shù)需要n-1遍排序;每突破冒泡排序的變形2.冒泡排序的變形一(升序)Fori=1Ton-1Forj=nToi+1Step-1Ifa(j)<a(j-1)Thentemp=a(j-1):a(j-1)=a(j):a(j)=tempEndIfNextjNexti74突破冒泡排序的變形2.冒泡排序的變形一(升序)19突破冒泡排序的變形排序思想解析:與標(biāo)準(zhǔn)式唯一的差異就是兩個(gè)比較項(xiàng)從a(j-1)和a(j)變成a(j+1)和a(j),因此循環(huán)語句也從“Forj=nToi+1Step-1”變成了

“Forj=n-1ToiStep-1”,本質(zhì)上排序過程,與標(biāo)準(zhǔn)式是完全一樣的。75突破冒泡排序的變形排序思想解析:與標(biāo)準(zhǔn)式唯一的差異就是兩個(gè)突破冒泡排序的變形3.冒泡排序的變形二(升序)Fori=1Ton-1Forj=1Ton-iIfa(j+1)<a(j)Thentemp=a(j+1):a(j+1)=a(j):a(j)=tempEndIfNextjNexti76突破冒泡排序的變形3.冒泡排序的變形二(升序)21突破冒泡排序的變形排序思想解析:跟標(biāo)準(zhǔn)型不一樣的是本代碼中每一遍冒泡是從前往后兩兩比較的,因此每一遍排序達(dá)到的效果是把最大值推到了最后面。第一遍排序后,最大值就到了最后位置,第二遍后,次大值就到了倒數(shù)第二個(gè)位置……。排序過程中,是后面的數(shù)據(jù)先排好,因此每一遍排序的初值都是1,后面的數(shù)隨著一遍遍的排序慢慢排好了,因此終值是變化的,為n-i。77突破冒泡排序的變形排序思想解析:跟標(biāo)準(zhǔn)型不一樣的是本代碼中突破冒泡排序的變形4.冒泡排序的變形三(升序)Fori=1Ton-1Forj=i+1TonIfa(j)<a(i)Thentemp=a(j):a(j)=a(i):a(i)=tempEndIfNextjNexti78突破冒泡排序的變形4.冒泡排序的變形三(升序)23突破冒泡排序的變形排序思想解析:在第i遍的排序中,把第i+1到第n個(gè)數(shù)依次與a(i)比較,如果比a(i)小,則交換。它的最大特點(diǎn)是:永遠(yuǎn)跟一個(gè)固定位置上的數(shù)去比較。排序過程中,是前面的數(shù)據(jù)先排好。79突破冒泡排序的變形排序思想解析:在第i遍的排序中,把第i+突破冒泡排序的變形5.冒泡排序的錯(cuò)誤變形Fori=1Ton-1Forj=iTon-1Ifa(j+1)<a(j)Thentemp=a(j+1):a(j+1)=a(j):a(j)=tempEndIfNextjNexti80突破冒泡排序的變形5.冒泡排序的錯(cuò)誤變形25突破冒泡排序的變形錯(cuò)誤原因解析:從語句“Forj=iTon-1”可看出每一遍的冒泡過程是把最大值從前往后推,因此排序過程中,是后面的數(shù)據(jù)先排好,前面的數(shù)據(jù)是亂的,但是第i遍的冒泡過程是從第i個(gè)數(shù)開始的,因此i位置前面的數(shù)據(jù)不能參與排序。而后面的數(shù)據(jù)已經(jīng)排好的,其實(shí)是不需要參與排序的。因此要改成“Forj=1Ton-i”81突破冒泡排序的變形錯(cuò)誤原因解析:從語句“Forj=iT突破冒泡排序的變形6.冒泡排序的優(yōu)化當(dāng)某一遍排序過程中沒有數(shù)據(jù)交換,說明數(shù)據(jù)已經(jīng)有序,無需進(jìn)行下一遍排序。代碼如下:DimflagAsBooleani=1flag=True

flag值為True表示一遍加工中發(fā)生過交換DoWhilei<=n-1Orflag=trueflag=False82突破冒泡排序的變形6.冒泡排序的優(yōu)化27突破冒泡排序的變形Forj=nToi+1Step-1Ifa(j)<a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEndIfNextji=i+1Loop83突破冒泡排序的變形Forj=nToi+1Step突破冒泡排序的變形思想解析:用一個(gè)邏輯變量flag標(biāo)記某一遍排序過程中是否有數(shù)據(jù)交換,如果沒有,則無需再進(jìn)行下一遍排序。排序遍數(shù)是i-1遍。另一種寫法:DimflagAsBooleanFori=1ton-1flag=falseForj=nToi+1Step-1Ifa(j)<a(j-1)Then84突破冒泡排序的變形思想解析:用一個(gè)邏輯變量flag標(biāo)記某一突破冒泡排序的變形k=a(j):a(j)=a(j-1):a(j-1)=kflag=TrueEndIfNextjIfflag=falsethenexitforNexti注意:這種寫法的排序遍數(shù)是i次,因?yàn)槌绦驈闹虚g跳出循環(huán),不執(zhí)行“nexti”指令,因此沒有多加一次。85突破冒泡排序的變形k=a(j):a(j)=a(j-1典題精練例1對(duì)于a數(shù)組排序的程序段如下:Fori=1Ton-1Forj=nToi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-l)=tEndIfNextjNexti86典題精練例1對(duì)于a數(shù)組排序的程序段如下:31典題精練則下列程序段運(yùn)行后,a數(shù)組的排序情況與上面程序段運(yùn)行結(jié)果不同的是(D)87Fori=1Ton-1Forj=1Ton-iIfa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNextiFori=1Ton-1Forj=i+1TonIfa(i)>a(j)Thent=a(i):a(i)=a(j):a(j)=tEndIfNextjNextiAB典題精練則下列程序段運(yùn)行后,a數(shù)組的排序情況與上面程序段運(yùn)行典題精練88Fori=1Ton-1Forj=n-1ToiStep-1Ifa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNextiFori=1Ton-1Forj=iTon-1Ifa(j+1)<a(j)Thent=a(j):a(j)=a(j+1):a(j+1)=tEndIfNextjNextiCD典題精練33Fori=1Ton-1Fori=1To典題精練解析

題干中的程序是冒泡排序,從后往前,小的元素上冒,最終實(shí)現(xiàn)升序排序。A選項(xiàng)是從前往后,大的元素下沉,實(shí)現(xiàn)升序排序。B選項(xiàng),程序第i趟加工即將第i個(gè)數(shù)據(jù)和后面的每個(gè)數(shù)據(jù)比較一遍,使得第i個(gè)數(shù)據(jù)比它后面的每個(gè)數(shù)據(jù)都小,所以也是升序。C選項(xiàng)和題干一樣,只是變化了一下循環(huán)變量的表示方式。D選項(xiàng)是從前往后比,大的元素下沉,但是它除了第一趟把所有的數(shù)據(jù)比較了一遍,從第二趟開始,比較的位置就發(fā)生了錯(cuò)誤,前面的數(shù)據(jù)沒有比較。所以答案選D。89典題精練解析題干中的程序是冒泡排序,從后往前,小的元素上冒典題精練例2冒泡排序在某一遍加工過程中沒有數(shù)據(jù)交換時(shí),說明數(shù)據(jù)己經(jīng)有

序,優(yōu)化程序段如下:i=1:flag=TrueDoWhilei<=4Andflag=Trueflag=FalseForj=5Toi+1Step-1Ifa(j)>a(j-1)Thent=a(j):a(j)=a(j-l):a(j-l)=t90典題精練例2冒泡排序在某一遍加工過程中沒有數(shù)據(jù)交換時(shí),說明典題精練flag=TrueEndIfNextji=i+1Loop數(shù)組元素a(l)到a(5)的值依次為“48,36,24,97,77”,經(jīng)過該程序段“加

工”后,變量i的值是

(

)A.1B.2C.3D.491典題精練flag=True36典題精練flag=TrueEndIfNextji=i+1Loop數(shù)組元素a(l)到a(5)的值依次為“48,36,24,97,77”,經(jīng)過該程序段“加

工”后,變量i的值是

(D)A.1B.2C.3D.492典題精練flag=True37典題精練解析

本題解題的關(guān)鍵在于理解變量flag的作用。邏輯類型變量flag用于標(biāo)記排序過程中數(shù)據(jù)是否有過交換,如果有交換,值為True否則為False。變量i為排序的趟數(shù),從內(nèi)循環(huán)看是降序排序,從后往前,大的元素上冒,因此經(jīng)過兩趟排序后數(shù)組a中的元素有序,第三趟時(shí)i初始值為3,數(shù)據(jù)沒有交換,但再一次執(zhí)行了i=i+1這一語句,所以i=4,當(dāng)i=4時(shí),由于前一趟數(shù)據(jù)沒有交換,flag=False,結(jié)束循環(huán)。所以答案選D。93典題精練解析本題解題的關(guān)鍵在于理解變量flag的作用。94真題在線39真題在線真題在線1.(2017浙江11月選考,16,3分)小李基于冒泡排序算法編寫了一個(gè)VB程序,功能如下:在文本框Text1中顯示排序前的數(shù)據(jù),單擊“排序”按鈕Command1,在文本框Text2中顯示剔除重復(fù)數(shù)據(jù)后的升序排序結(jié)果。程序運(yùn)行界面如圖所示。95真題在線1.(2017浙江11月選考,16,3分)小李基于冒真題在線實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正。Constn=10Dima(1Ton)AsIntegerPrivateSubCommand1_Click()DimiAsInteger,jAsInteger,tAsIntegerDimbottomAsInteger剔除重復(fù)數(shù)據(jù)后元素的個(gè)數(shù)’獲取排序前數(shù)據(jù)依次存儲(chǔ)在數(shù)組a中,并在文本框Text1中顯示。代碼略96真題在線實(shí)現(xiàn)上述功能的VB代碼如下,但加框處代碼有錯(cuò),請(qǐng)改正真題在線bottom=ni=1DoWhilei<=bottom-1Forj=bottomToi+1Step-1Ifa(j)<a(i)Then(1)t=a(j):a(j)=a(j-1):a(j-1)=tElseIfa(j)=a(j-1)Then若相鄰兩個(gè)數(shù)據(jù)相等,進(jìn)行剔除處理97真題在線bottom=n42真題在線

a(bottom)=a(j)(2)bottom=bottom-1EndIfNextji=i+1Loop98真題在線 a(bottom)=a(j)(2)43真題在線Text2.Text=“”Fori=1TobottomText2.Text=Text2.Text+Str(a(i))NextiEndSub99真題在線Text2.Text=“”44真題在線答案(1)a(j)<a(j-1)(或a(j-1)>