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

排序算法的程序?qū)崿F(xiàn)排序算法——冒泡排序所謂冒泡排序，形象的說，就是在將一組數(shù)據(jù)從小到大的順序排列時(shí)，小的數(shù)據(jù)視為質(zhì)量較輕，大的數(shù)據(jù)視為質(zhì)量較重，小的數(shù)據(jù)好比水中的氣泡，往上方移動，較大的數(shù)據(jù)好比是石頭，往下沉，最重的會沉到底，最輕的會浮到頂，反復(fù)進(jìn)行比較，直到數(shù)據(jù)列排成有序列。實(shí)例分析請將下列數(shù)據(jù)按從大到小的順序，利用冒泡法排序。｛30,38,65,97,76,13,27,49}1排序號：數(shù)據(jù)序號12345678原始數(shù)據(jù)30386597761327492排序數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)現(xiàn)將8號數(shù)據(jù)49和7號數(shù)據(jù)27比較，因?yàn)?9>27所以，49和27的位置互換，變?yōu)椋篿=1：第一次排序j=8：第一步：8號、7號排序49271376976538304927137697653830t49t=d(8):d(8)=d(7):d(7)=t數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)j=7：第二步：7號6號排序4927137697653830現(xiàn)將7號數(shù)據(jù)49和6號數(shù)據(jù)13比較，因?yàn)?9>13所以，49和13的位置互換，變?yōu)椋?927137697653830t49t=d(7):d(7)=d(6):d(6)=tj=6：第三步：比較6、5號數(shù)據(jù)j=5：第四步比較5、4號數(shù)據(jù)方法同第三步，因?yàn)?6<97所以數(shù)據(jù)順序不變。數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)1327497697653830現(xiàn)將6號數(shù)據(jù)49和5號數(shù)據(jù)76比較，因?yàn)?9<76所以，49和76的位置不互換。1327497697653830j=4：第五步：比較4、3號數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)1327497697653830現(xiàn)將4號數(shù)據(jù)97和3號數(shù)據(jù)65比較，因?yàn)?7>65所以，97和65的位置互換。1327497697653830t

97t=d(4):d(4)=d(3):d(3)=tj=3：第六步：比較3、2號數(shù)據(jù)：數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)1327497665973830現(xiàn)將3號數(shù)據(jù)97和2號數(shù)據(jù)38比較，因?yàn)?7>38所以，97和38的位置互換。1327497665973830t

97t=d(3):d(3)=d(2):d(2)=tj=2第七步：比較2、1號數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)1327497665389730現(xiàn)將2號數(shù)據(jù)97和1號數(shù)據(jù)30比較，因?yàn)?7>30所以，97和30的位置互換。1327497665389730t97t=d(2):d(2)=d(1):d(1)=t這樣就完成了第一次排序，它的基本特征是將最大數(shù)排到了最左邊，然后再從第8個(gè)開始，進(jìn)行第二次排序，將第二大的數(shù)據(jù)排到了第二位，反復(fù)下去，就可以完成排序。一共要進(jìn)行7次才能完成。數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)數(shù)據(jù)序號12345678原始數(shù)據(jù)1327497665383097經(jīng)過第二次排序，數(shù)據(jù)順序應(yīng)該是什么樣的？2713496538307697經(jīng)過第三次呢？2713493830657697算法分析第1次冒泡排序時(shí)(i=1)

j從8開始到2Forj=8to2step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值第2次冒泡排序時(shí)(i=2)

j從8開始到3Forj=8to3step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值第3次冒泡排序時(shí)(i=3)

j從8開始到4Forj=8to4step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值當(dāng)i從1到7變化時(shí)每次j從8到i+1時(shí)

d(j)>d(j-1)時(shí),則交換它們第4次冒泡排序時(shí)(i=4)

j從8開始到5Forj=8to5step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值第5次冒泡排序時(shí)(i=5)

j從8開始到6Forj=8to6step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值第6次冒泡排序時(shí)(i=6)

j從8開始到7Forj=8to7step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值第7次冒泡排序時(shí)(i=7)

j從8開始到8Forj=8to8step-1ifd(j)<d(j-1)then交換d(j)和d(j-1)的值說明1.冒泡法排序完成n個(gè)數(shù)據(jù)的一次排序需要n-1趟比較，完成整個(gè)排序需要n*(n-1)/2次比較，對于數(shù)據(jù)較多時(shí)，計(jì)算量很大。2.有些數(shù)據(jù)的冒泡法排序可能用更少的步驟可以完成，后面的步驟可能毫無意義，但計(jì)算機(jī)必須完成。3.交換數(shù)據(jù)時(shí)注意引入第三方變量。提高：如果要對有n個(gè)元素的數(shù)組進(jìn)行排序，那么要進(jìn)行________輪冒泡，其中外循環(huán)變量i從

到

變化，內(nèi)循環(huán)變量j從

到

變化。

n-11n-1ni+1a(1)、a(2)、a(3)、…a(n-2)、a(n-1)、a(n)總結(jié)(以降序?yàn)槔?數(shù)組d（1ton）Fori=1Ton-1（i：n個(gè)數(shù)排序共需進(jìn)行n-1趟）Forj=nToi+1Step-1（j：控制元素對比與交換）ifd(j)>d(j-1)then（每一趟從后往前，數(shù)據(jù)比較）t=d(j):d(j)=d(j-1):d(j-1)=t（滿足條件，數(shù)據(jù)交換）NextjNexti思考：如果以升序進(jìn)行冒泡排序，劃線處的程序代碼

如何修改？

1、今年北京奧運(yùn)會有七個(gè)國家或地區(qū)參加，開幕式按照國家或地區(qū)英文名從小到大的次序出場，已知這七個(gè)國家或地區(qū)的名字，請寫出經(jīng)前三趟冒泡后出場的次序表。

England,France,American，Italy,Japan,China,Hongkong1234567EnglandFranceAmericanItalyJapanChinaHongkong課堂練習(xí)1234567AmericanChinaEnglandFranceHongkongItalyJapan2、對“648251”中的6個(gè)數(shù)碼進(jìn)行兩趟冒泡排序后即為某游戲中數(shù)字密碼鎖的密碼，該密碼是（）。

A）684521B）462518C）126485D