冒泡排序算法

關(guān)于冒泡排序算法第一頁，共十七頁，2022年，8月28日情景：1.觀察水中的氣泡往上冒的情景，氣泡往上冒的時(shí)候有什么特點(diǎn)呢？2.第一次上體育課集隊(duì)的時(shí)候體育老師是怎么樣幫我們按身材的高低順序進(jìn)行排隊(duì)的？

第二頁，共十七頁，2022年，8月28日冒泡原理冒泡排序和氣泡在水中不斷往上冒的情況有些類似。氣泡大的（大的數(shù)據(jù)）在下面，氣泡小的（小的數(shù)據(jù)）在上面。冒泡排序的基本原理是對存放原始數(shù)據(jù)的數(shù)組，按從前往后的方向進(jìn)行多次掃描，每次掃描稱為一趟。當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排序要求的大小次序不符合時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會逐個(gè)向前移動，好象氣泡向上浮起一樣。第三頁，共十七頁，2022年，8月28日例：用冒泡排序的方法將下面一組無序數(shù)組排成從小到大{49,38,65,97,76,13,27,49}分析：首先為了方便分析，我們把所給的數(shù)據(jù)先用一個(gè)表格列出來，如下：第四頁，共十七頁，2022年，8月28日對比原數(shù)據(jù)經(jīng)過第一趟排序，實(shí)現(xiàn)了什么目的？第一趟排序，一共進(jìn)行了多少次比較？4927137697653849數(shù)據(jù)87654321序號49>38,交換位置原數(shù)據(jù)和序號序號12345678數(shù)據(jù)4938659776132749第一趟排序的步驟：序號12345678數(shù)據(jù)3849659776132749序號12345678數(shù)據(jù)3849659776132749序號12345678數(shù)據(jù)3849659776132749序號12345678數(shù)據(jù)3849657697132749序號12345678數(shù)據(jù)3849657613972749序號12345678數(shù)據(jù)3849657613279749序號12345678數(shù)據(jù)3849657613274997經(jīng)過第一趟排序，把最大的數(shù)沉到最底了！49<65,保持不變65<97,保持不變97>76,交換位置97>13,交換位置97>27,交換位置97>49,交換位置第五頁，共十七頁，2022年，8月28日經(jīng)過第二趟排序，實(shí)現(xiàn)了什么目的？經(jīng)過第二趟排序，把第二大的數(shù)沉到倒數(shù)第二個(gè)位置了!9749271376654938數(shù)據(jù)87654321序號38<49,保持不變第一趟排序后的數(shù)據(jù)和序號第二趟排序的步驟：序號12345678數(shù)據(jù)384965761327499749<65,保持不變65<76,保持不變76>13,交換位置76>27,交換位置76>49,交換位置序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849651376274997序號12345678數(shù)據(jù)3849651327764997序號12345678數(shù)據(jù)384965132749769776<97,保持不變序號12345678數(shù)據(jù)3849651327497697第六頁，共十七頁，2022年，8月28日觀察原數(shù)據(jù)與第一、二趟排序后的數(shù)據(jù)序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849651327497697序號12345678數(shù)據(jù)4938659776132749問：為了使這一組無序數(shù)組完全按照要求排成從小到大我們還需不需要再繼續(xù)排序呢？問：那么我們預(yù)計(jì)最多一共要經(jīng)過多少次排序呢？第七頁，共十七頁，2022年，8月28日例題：下面我們繼續(xù)考慮，將我們剛才排序的全過程用算法流程圖表示出來。我們把它分成幾步來做，第一步，先把第一趟的排序用流程圖描述出來。第八頁，共十七頁，2022年，8月28日R[1]:=R[2]t:=R[1]R[1]:=R[2]R[2]:=t開始1.畫出第一趟排序的算法流程圖：假設(shè)該數(shù)據(jù)列為R[1],R[2],R[3],R[4],R[5],R[6],R[7],R[8]第一步做什么？R[1]>R[2]是否如何交換數(shù)據(jù)，這樣行嗎？R[2]>R[3]是否t:=R[2]R[2]:=R[3]R[3]:=t…不斷的這樣畫下去要畫多少個(gè)類似的選擇結(jié)構(gòu)？有沒有辦法讓流程圖更加簡潔呢？這樣交換數(shù)據(jù)，會有什么問題？分析：第九頁，共十七頁，2022年，8月28日R[1]>R[2]R[1]=R[2]是否t=R[1]R[1]=R[2]R[2]=t否是i:=i+1結(jié)束開始R[1]>R[2]R[1]=R[2]是否t=R[1]R[1]=R[2]R[2]=ti:=1R[i]>R[i+1]i>7t:=R[i]R[i]:=R[i+1]R[i+1]:=t分析：1.畫出第一趟排序的算法流程圖：用簡潔的循環(huán)結(jié)構(gòu)進(jìn)行表示第十頁，共十七頁，2022年，8月28日否是i:=i+1結(jié)束開始R[1]>R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=ti:=1R[i]>R[i+1]t:=R[i]R[i]:=R[i+1]R[i+1]:=ti>7分析：后面的排序只要按照這種方法不斷進(jìn)行就行了。2、按照這種畫法第二趟、第三趟、第四趟排序的流程圖怎樣畫？怎樣把整個(gè)冒泡排序的流程圖畫出來？那么同樣的結(jié)構(gòu)要進(jìn)行多少次呢？有沒有辦法讓流程圖更加簡潔呢？第十一頁，共十七頁，2022年，8月28日是3、怎樣把整個(gè)冒泡排序的流程圖畫出來？開始結(jié)束j>7j:=1否j:=j＋1是i>7否i:=1i:=i+1是否R[i]>R[i+1]t:=R[i]R[i]:=R[i+1]R[i+1]:=t分析：這是一個(gè)兩重循環(huán)結(jié)構(gòu)第十二頁，共十七頁，2022年，8月28日思考交流：在我們剛才的算法流程圖中，每一趟的排序我們都進(jìn)行了7次，是否每一趟的排序都需要進(jìn)行7次比較呢？那么現(xiàn)在請你對我們剛才畫出的算法流程圖進(jìn)行優(yōu)化，設(shè)計(jì)出更好的流程圖避免不必要的工作。第十三頁，共十七頁，2022年，8月28日觀察原數(shù)據(jù)與第一、二趟排序后的數(shù)據(jù)序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849651327497697序號12345678數(shù)據(jù)4938659776132749我們知道經(jīng)過第一趟的排序之后，最大的一個(gè)數(shù)已經(jīng)排到最后了這樣在進(jìn)行第二趟排序時(shí)有沒有必要再對第7、8個(gè)數(shù)據(jù)再進(jìn)行排序呢？第十四頁，共十七頁，2022年，8月28日參照我們第一趟排序的畫法、第二趟排序的流程圖此時(shí)只需進(jìn)行6次。否是i:=i+1結(jié)束開始R[1]>R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=ti:=1R[i]>R[i+1]t:=R[i]R[i]:=R[i+1]R[i+1]:=ti>7否是i:=i+1結(jié)束開始R[1]>R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=ti:=1R[i]>R[i+1]t:=R[i]R[i]:=R[i+1]R[i+1]:=ti>6分析：第十五頁，共十七頁，2022年，8月28日否是i>j那么我們可以把整