浙教版高中信息技術(shù)-選修1-23-排序課件

第二單元排序算法及程序?qū)崿F(xiàn)下表記錄了6個數(shù)據(jù)的排序過程。分析表中數(shù)據(jù)可知,該排序采用的算

法與排序方式分別為

()A.冒泡排序,降序B.選擇排序,降序C.冒泡排序,升序D.選擇排序,升序原始數(shù)據(jù)655759444569第1遍446557594569第2遍444565575969第3遍444557655969…………………排序是一種算法思想（對已有的一組數(shù)，經(jīng)過一系列的加工處理后輸出一組目標(biāo)數(shù)）。什么是排序（sort）就是把雜亂無章的數(shù)據(jù)變?yōu)橛行虻臄?shù)據(jù)的過程。（遞增或遞減）。生活和工作中對問題的處理過程更多的依賴于數(shù)據(jù)的有序性。比如說學(xué)生的成績。校園歌手打分評委1評委2評委3評委4評委5評委69.59.09.69.79.69.4評委1評委2評委3評委4評委5評委69.59.09.69.79.69.4d(1)d(2)d(3)d(4)d(5)d(6)9.09.49.59.69.69.7d(1)d(2)d(3)d(4)d(5)d(6)排序d(1)=9.5d(2)=9.0d(3)=9.6d(4)=9.7d(5)=9.6d(6)=9.4排序Fori=1to6List1.additem

d(i)Nexti冒泡排序冒泡排序是在一列數(shù)據(jù)中把較小（大）的數(shù)據(jù)逐次向上推移的一種排序技術(shù)。（1）N個元素垂直堆放一列（2）從最下面的一個元素起，自下而上比較相鄰兩個元素，將小的元素換到上面（3）重復(fù)這一過程，直到處理完最后的兩個元素

結(jié)果：第一遍加工結(jié)束，最小的元素會升到第一個元素的位置對剩下的n-1個元素重復(fù)2-3步驟，這是第二遍加工，第二小的元素會上升到第二個元素的位置……但比較的數(shù)據(jù)會逐個減少，直至只剩下最后的兩個元素的比較和交換?；舅枷耄好芭菖判虻倪^程請觀察第一、二遍共比較幾次，交換幾次，請問第三、四、五遍的結(jié)果

第一遍加工第二遍加工

原始數(shù)據(jù)123451234A(1)40404040402020202020A(2)30303030204040404025A(3)70707020303030302540A(4)25252070707070253030A(5)20202525252525707070A(6)55555555555555555555冒泡排序的數(shù)據(jù)比較次數(shù)對于規(guī)模為n的數(shù)據(jù)進行排序，總共需進行n-1遍加工。第一遍加工的比較次數(shù)為n-1次；第二遍加工的比較次數(shù)為n-2次；……第n-1遍加工的比較次數(shù)為1次。所以總比較次數(shù)：n(n-1)/2次冒泡排序的數(shù)據(jù)交換次數(shù)當(dāng)i<j時，a(i)>a(j)，就稱a(i)和a(j)為一個逆序?qū)?。?shù)列中逆序?qū)Φ膶?shù)=數(shù)據(jù)的交換次數(shù)例：數(shù)列403070252055中存在的逆序?qū)τ袛?shù)據(jù)的交換次數(shù)為9次。(40,30)(40,25)(40,20)(30,25)(30,20)(70,25)(70,20)(70,55)(25,20)有如下一組數(shù)據(jù)：27166853673127159，利用冒泡排序進行從小到大排序，需要交換的次數(shù)是A、5B、6C、7D、8第一遍：27361668573127159交換兩次第二遍：27367316685127159交換兩次第三遍：27367385166127159交換一次第四遍：27367385127166159交換一次第五遍：27367385127159166交換一次第六遍：27367385127159166無交換冒泡排序算法的程序?qū)崿F(xiàn)冒泡排序的過程變量分析，及過程歸納n表示排序數(shù)據(jù)的個數(shù)；i表示加工處理（冒泡）的遍數(shù)；j表示當(dāng)前訪問數(shù)據(jù)的下標(biāo)（相當(dāng)于指針）；處理過程(i)比較對象

（交換）訪問數(shù)據(jù)范圍

(j）處理成效第1遍(i=1)d(j)與d(j-1)，若逆序則交換N到2（i+1）推出最小的數(shù)據(jù)到1號位置第i遍d(j)與d(j-1)，若逆序則交換N到i+1推出第i小的數(shù)據(jù)到i位置…………第n-1遍d(j)與d(j-1)，若逆序則交換N到N推出第n-1小的數(shù)據(jù)到n-1位置(1)冒泡排序的代碼如下:Fori=1Ton-1

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

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

比較相鄰的兩個數(shù)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)。冒泡排序程序的實現(xiàn)可用雙重FOR循環(huán)來實現(xiàn)，外層FOR循環(huán)控制是第幾遍加工，內(nèi)層FOR循環(huán)控制進行排序的數(shù)組元素下標(biāo)的變化范圍。由于每趟加工完成后，進行排序的范圍會發(fā)生變化（每趟減少一個），故內(nèi)層FOR循環(huán)變量的下界由外層循環(huán)變量決定。例1

(2012浙江3月高考,3,3分)實現(xiàn)某排序算法的部分VB程序如下:Fori=1To4Forj=5Toi+1Step-1Ifa(j)<a(j-1)Thent=a(j):a(j)=a(j-1):a(j-1)=tNextjNexti在經(jīng)過某一遍排序“加工”后,數(shù)組元素a(1)到a(5)的數(shù)據(jù)依次為“28,7

0,53,57,30”。則下一遍排序“加工”后數(shù)組元素a(1)到a(5)的數(shù)據(jù)應(yīng)該

是

()A.28,30,70,53,57B.28,30,53,57,70C.28,30,57,53,70D.28,30,53,70,57s=“”Fori=1to3

Forj=7toi+1step-1

Ifa(j)<a(j-1)then

k=a(j):a(j)=a(j-1):a(j-1)=k

endif

nextjs=s+str(a(i))NextIText1.text=s數(shù)組元素a(1)到a(7)的數(shù)據(jù)一次為3，9，1，5，8，6，2，經(jīng)過該程序段加工后，文本框Text1中顯示的內(nèi)容是（）A、123B、986C、391D、862A加工三遍冒泡排序算法采用冒泡排序算法對數(shù)組a中的5個數(shù)據(jù)“5，10，6，30，9”進行排序，部分程序如下：Fori=1to4Forj=5toi+1step-1Ifa(j)<a(j-1)thenEndifNextjNextI以上程序是以

方式排序的，框內(nèi)的語句共執(zhí)行了

次。t=a(j):a(j)=a(j-1):a(j-1)=t冒泡算法的程序優(yōu)化Fori=1Ton-1flag=0Forj=nToi+1Step-1Ifa(j)<a(j-1)Thenk=a(j):a(j)=a(j-1):a(j-1)=k:flag=1EndIfNextj

Ifflag=0ThenExitFor

Nexti只要在某遍排序中（內(nèi)循環(huán)）沒有交換，則說明待排序的無序區(qū)中已經(jīng)有序，排序過程可在此趟排序后終止。用冒泡排序?qū)?，5，6，3，2，1進行從小到大排序，第三遍加工后的狀態(tài)為：A、4，5，3，2，1，6B、4，3，2，1，5，6C、3，2，1，4，5，6D、2，1，3，4，5，6第1遍：4，5，3，2，1，6第2遍：4，3，2，1，5，6第3遍：3，2，1，4，5，6第4遍：2，1，3，4，5，6第5遍：1，2，3，4，5，6冒泡排序并非一定得從最底部開始冒泡，還可以從頂部往下沉。自上而下的冒泡Fori=nto2step-1Forj=1toi-1Ifa(j)>a(j+1)thenK=a(j):a(j)=a(j+1):a(j+1)=kEndifNextjNextiFori=1Ton-1Forj=1Ton-iFori=1to2Forj=1to6-iIfa(j)<a(j+1)thenK=a(j):a(j)=a(j+1):a(j+1)=kEndifNextjNexti數(shù)組a(1)~a(6)的值依次為71，54，58，29，31，78，則最后結(jié)束為：A.29，31，54，58，71，78B.78，71，58，54，31，29C.54，29，31，58，71，78D.71，58，54，78，31，29選擇排序選擇排序的基本思想：

在參加排序數(shù)組的所有元素中找出最?。ɑ蜃畲螅?shù)據(jù)的元素，使它與第一個元素中的數(shù)據(jù)相互交換位置。然后在余下的元素中，找出最?。ɑ蜃畲螅?shù)據(jù)的元素與第二個元素中的數(shù)據(jù)相互交換位置。以此類推，直至所有元素成為一個有序的序列。位置重排Dimd（1to6）asinteger

數(shù)組dd(1)d(2)d(3)d(4)d(5)D(6)982116734365162198734365162198734365162143739865162143659873162143657398選擇排序1.按日期先后整理一堆文件的算法是:第一次,在這疊文件中從上到下找

出日期最早的文件反扣在桌面上;第二次從剩余文件中從上到下找出日

期最早的文件反扣在第一次找出的文件上;第三次,從剩余文件中從上到

下找出日期最早的文件反扣在第二次找出的文件上;……,依此類推,最后

完成整理工作。此算法屬于

()A.選擇排序B.對分查找C.遞歸算法D.冒泡排序3.經(jīng)過某一遍排序“加工”后，數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為“10，41，75，12，63，11，85”。則下一遍排序“加工”后數(shù)組元素a(1)到a(7)的數(shù)據(jù)依次為：例3

(2010浙江6月會考,3分)某校通過政府招投標(biāo)中心采購一套多媒體

教學(xué)設(shè)備,有5家單位參加競標(biāo),競標(biāo)價分別為19萬、15萬、21萬、13

萬、12萬元人民幣。若采用選擇排序算法對標(biāo)價從大到小排序,需要進

行數(shù)據(jù)互換的次數(shù)是

()A.1B.2C.3D.4(2011浙江6月會考,3分)用選擇排序法對一組學(xué)生的身高數(shù)據(jù)進行升序排序,已知第一遍排序結(jié)束后的數(shù)據(jù)序列為165,168,178,175,171,則下列選項中可能是原始數(shù)據(jù)序列的是(

)A.175,178,168,165,171

B.178,168,165,175,171C.165,178,168,175,171

D.165,168,171,175,178選擇排序的程序?qū)崿F(xiàn)怎么找到最小數(shù)？第一遍

i=1（k=1）j從2到6若d(j)<d(k),則讓k=j第二遍

i=2（k=2）j從3到6若d(j)<d(k),則讓k=j第三遍

i=3（k=3）j從4到6若d(j)<d(k),則讓k=j第四遍

i=4（k=4）j從5到6若d(j)<d(k),則讓k=j第五遍

i=5（k=5）j從6到6若d(j)<d(k),則讓k=j第i遍

（k=i）j從i+1到6若d(j)<d(k),則讓k=j數(shù)組dd(1)d(2)d(3)d(4)d(5)D(6)982116734365

選擇排序的代碼如下:Fori=1Ton-1k=iForj=i+1TonIfa(j)<a(k)Thenk=j

NextjIfk<>iThentemp=a(i):a(i)=a(k):a(k)=tempEndIfNexti說明:①虛線框內(nèi)代碼用于尋找數(shù)組元素a(i)到a(n)的最小值,變量k記錄

當(dāng)前找到的最小值的位置,即數(shù)組元素的下標(biāo),則a(k)就是當(dāng)前找到的最

小的數(shù)組元素。它的思想方法是先假設(shè)數(shù)組的第i項是最小的(第i遍排序),因此k記為i,然后把從第i+1項開始的所有數(shù)組元素跟a(k)進行比較,如

果比a(k)小,則用k記錄該元素的下標(biāo)。這樣循環(huán)結(jié)束后,變量k中存儲的

就是數(shù)組中從第i項至第n項的最小元素的下標(biāo),a(k)就是第i項至第n項中

的最小元素。②從小到大排序時,If語句中條件表達式為:a(j)<a(k);從大到小排序時,If語句中條件表達式為:a(j)>a(k)。(2012浙江3月高考,9,2分)對數(shù)組元素a(1)到a(8)進行升序排序,其排序算法的VB部分程序段如下:For

m=1

To

7

p=m

For

n=m+1

To

8

Next

n

If

p<>m

Then

t=a(p):a(p)=a(m):a(m)=tNext

m方框中的語句是(

)A.If

a(n)<a(p)

Then

p=mB.If

a(n)<a(p)

Then

p=nC.If

a(n)>a(p)

Then

p=nD.If

a(n)>a(p)

Then

p=mi=1Dowhilei<=n-1k=iJ=k+1Dowhilej<=nIfa(k)<a(j)thenk=jj=j+1LoopIfk<>ithenT=a(k):a(k)=a(i):a(i)=tEndifi=i+1LoopForI=1tonList2.additemstr(a(i))NextIDima(1to100)asinteger,I,j,t,kasintegerConstn=100Privatesubcommand1_click()i=0Dowhilei>n-1i=i+1k=iJ=k+1Dowhilej<=nIfa(k)<a(j)thenk=jk=k+1LoopIfk<>ithenT=a(k):a(k)=a(i):a(i)=tEndifLoopFori=1tonList2.additemstr(a(i))NextiEndsub下劃線的代碼有錯誤怎么找到最小數(shù)？數(shù)組dd(1)d(2)d(3)d(4)d(5)D(6)982116734365程序?qū)崿F(xiàn)(從后向前，升序)第一遍

i=n（k=n）j從n-1到1若d(j)>d(k),則