冒泡排序課件

第9章排序算法

——冒泡排序情景：觀察水中的氣泡往上冒的情景，有什么特點呢？冒泡原理冒泡排序和氣泡在水中不斷往上冒的情況有些類似。氣泡大的（大的數(shù)據(jù)）在下面，氣泡小的（小的數(shù)據(jù)）在上面。冒泡排序的基本原理對存放原始數(shù)據(jù)的數(shù)組，按從前往后的方向進行多次掃描，每次掃描稱為一趟。當(dāng)發(fā)現(xiàn)相鄰兩個數(shù)據(jù)的次序與排序要求的大小次序不符合時，即將這兩個數(shù)據(jù)進行互換。這樣，較小的數(shù)據(jù)就會逐個向前移動，好象氣泡向上浮起一樣。例：用冒泡排序的方法將下面一組無序數(shù)組排成從小到大的順序。{49,38,65,97,76,13,27,49}分析：首先為了方便分析，我們把所給的數(shù)據(jù)先用一個表格列出來，如下：對比原數(shù)據(jù)經(jīng)過第一趟排序，實現(xià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,交換位置經(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觀察原數(shù)據(jù)與第一、二趟排序后的數(shù)據(jù)序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849651327497697序號12345678數(shù)據(jù)4938659776132749問：為了使這一組無序數(shù)組完全按照要求排成從小到大我們還需不需要再繼續(xù)排序呢？問：那么我們預(yù)計最多一共要經(jīng)過多少次排序呢？序號12345678數(shù)據(jù)3849132749657697序號12345678數(shù)據(jù)4938659776132749序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3813274949657697序號12345678數(shù)據(jù)1327384949657697序號12345678數(shù)據(jù)3849651327497697序號12345678數(shù)據(jù)1327384949657697序號12345678數(shù)據(jù)1327384949657697初始1趟2趟3趟4趟5趟6趟7趟例題：下面我們繼續(xù)考慮，將我們剛才排序的全過程用算法流程圖表示出來。我們把它分成幾步來做，第一步，先把第一趟的排序用流程圖描述出來。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ù)，會有什么問題？分析：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)進行表示否是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分析：后面的排序只要按照這種方法不斷進行就行了。2、按照這種畫法第二趟、第三趟、第四趟排序的流程圖怎樣畫？怎樣把整個冒泡排序的流程圖畫出來？那么同樣的結(jié)構(gòu)要進行多少次呢？有沒有辦法讓流程圖更加簡潔呢？是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)課堂思考：在我們剛才的算法流程圖中，每一趟的排序我們都進行了7次，是否每一趟的排序都需要進行7次比較呢？觀察原數(shù)據(jù)與第一、二趟排序后的數(shù)據(jù)序號12345678數(shù)據(jù)3849657613274997序號12345678數(shù)據(jù)3849651327497697序號12345678數(shù)據(jù)4938659776132749我們知道經(jīng)過第一趟的排序之后，最大的一個數(shù)已經(jīng)排到最后了這樣在進行第二趟排序時有沒有必要再對第7、8個數(shù)據(jù)再進行排序呢？擴展:1234’322964783445冒泡排序也可以從后往前進行，過程演示如下：小結(jié)：

本節(jié)課主要學(xué)習(xí)了冒泡排序的基本原理及其算法流程圖。其中數(shù)組和雙循環(huán)是我們本節(jié)課使用較多的一種結(jié)構(gòu)。應(yīng)用到本節(jié)知識的實例有很多，比如：打印九九乘法口訣表、彩票數(shù)字選擇器、工作表安排等等。課后作業(yè)：在剛才的冒泡排序中是否一定要進行7趟？針對這個問題你有什么好的方法對我們的算法再進行優(yōu)化？

下課了。。。休息一會兒。。。追說課一、說課題課題名稱：冒泡排序選用教材：《數(shù)據(jù)結(jié)構(gòu)》

西安交通大學(xué)出版社適用范圍：計算機及相關(guān)專業(yè)課題位置：第9章排序冒泡排序二、說對課題的分析與處理

1、地位作用2、目標(biāo)要求3、重點難點排序的方法設(shè)計中包含的豐富的程序設(shè)計技巧，這對初學(xué)者提高軟件設(shè)計能力幫助很大。而且本知識點也是后續(xù)學(xué)習(xí)“查找”的一個基礎(chǔ)。（1）認知方面：掌握冒泡排序的原理和流程圖；（2）技能方面：掌握冒泡排序的優(yōu)化方法；（3）情感方面：培養(yǎng)學(xué)習(xí)樂趣和解決實際問題應(yīng)用的能力。（1）重點：冒泡排序的原理；（2）難點：冒泡排序的優(yōu)化方法。三、教學(xué)對象分析1、本課題教學(xué)對象2、學(xué)生特點教育技術(shù)學(xué)專業(yè)本科大二學(xué)生（1）具備計算機的基礎(chǔ)知識；（2）具備基本的C程序的閱讀能力；（3）但是較計算機專業(yè)的學(xué)生來說，動手和獨立思考的能力教差。

四、說教學(xué)策略1、教學(xué)方法2、學(xué)法指導(dǎo)

（1）講解法——幫助學(xué)生理解較為抽象的課堂知識（2）舉例法——通過舉例，深入理解理論知識（3）討論法——針對課堂問題，討論優(yōu)化算法的策略（4）情景教學(xué)法倡導(dǎo)“自主、合作、探究”的學(xué)習(xí)方式，具體的學(xué)法是討論法。五、說講授程序

1、新課導(dǎo)入

結(jié)合之前學(xué)習(xí)的有關(guān)排序的概念、數(shù)組的概念以及循環(huán)算法的概念，并采用情景教學(xué)的方法，引入冒泡排序的基本原理。

這樣導(dǎo)