冒泡排序算法

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

第二頁，共十七頁，2022年，8月28日冒泡原理冒泡排序和氣泡在水中不斷往上冒的情況有些類似。氣泡大的（大的數(shù)據(jù)）在下面，氣泡小的（小的數(shù)據(jù)）在上面。冒泡排序的基本原理是對存放原始數(shù)據(jù)的數(shù)組，按從前往后的方向進(jìn)行多次掃描，每次掃描稱為一趟。當(dāng)發(fā)現(xiàn)相鄰兩個數(shù)據(jù)的次序與排序要求的大小次序不符合時，即將這兩個數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會逐個向前移動，好象氣泡向上浮起一樣。第三頁，共十七頁，2022年，8月28日例：用冒泡排序的方法將下面一組無序數(shù)組排成從小到大{49,38,65,97,76,13,27,49}分析：首先為了方便分析，我們把所給的數(shù)據(jù)先用一個表格列出來，如下：第四頁，共十七頁，2022年，8月28日對比原數(shù)據(jù)經(jīng)過第一趟排序，實現(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)過第二趟排序，實現(xiàn)了什么目的？經(jīng)過第二趟排序，把第二大的數(shù)沉到倒數(shù)第二個位置了!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ī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…不斷的這樣畫下去要畫多少個類似的選擇結(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、按照這種畫法第二趟、第三趟、第四趟排序的流程圖怎樣畫？怎樣把整個冒泡排序的流程圖畫出來？那么同樣的結(jié)構(gòu)要進(jìn)行多少次呢？有沒有辦法讓流程圖更加簡潔呢？第十一頁，共十七頁，2022年，8月28日是3、怎樣把整個冒泡排序的流程圖畫出來？開始結(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分析：這是一個兩重循環(huán)結(jié)構(gòu)第十二頁，共十七頁，2022年，8月28日思考交流：在我們剛才的算法流程圖中，每一趟的排序我們都進(jìn)行了7次，是否每一趟的排序都需要進(jìn)行7次比較呢？那么現(xiàn)在請你對我們剛才畫出的算法流程圖進(jìn)行優(yōu)化，設(shè)計出更好的流程圖避免不必要的工作。第十三頁，共十七頁，2022年，8月28日觀察原數(shù)據(jù)與第一、二趟排序后的數(shù)據(jù)序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849651327497697序號12345678數(shù)據(jù)4938659776132749我們知道經(jīng)過第一趟的排序之后，最大的一個數(shù)已經(jīng)排到最后了這樣在進(jìn)行第二趟排序時有沒有必要再對第7、8個數(shù)據(jù)再進(jìn)行排序呢？第十四頁，共十七頁，2022年，8月28日參照我們第一趟排序的畫法、第二趟排序的流程圖此時只需進(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那么我們可以把整