冒泡排序算法

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

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