前情回顧015.3.1認(rèn)識(shí)排序排序1排序的存儲(chǔ)結(jié)構(gòu)3排序的分類2如何排序4排序是指把一個(gè)任意序列的數(shù)據(jù)元素重新排列成按照某關(guān)鍵字遞增或遞減序列的過(guò)程穩(wěn)定排序和不穩(wěn)定排序內(nèi)部排序和外部排序順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)數(shù)組存儲(chǔ)講師：XXX5.3.2冒泡排序課堂導(dǎo)入02課堂導(dǎo)入024949386597761327現(xiàn)在有8個(gè)不同大小的桶，為支援縉云山山火，搬運(yùn)物資的“重慶崽兒”想把它們套在一起，盡可能節(jié)約搬運(yùn)物資車的空間，請(qǐng)你們幫幫他。（提示：將已有桶從小到大進(jìn)行排序，依次套在一起）假設(shè)桶為圓柱體，已給桶底半徑，單位（cm）熱身活動(dòng)03小組合作(5分鐘)嘗試用小組想到的方法對(duì)8個(gè)桶的桶底半徑進(jìn)行排序，完成學(xué)習(xí)單小組展示04第三組第五組VS為什么叫“冒泡”排序？冒泡排序和魚(yú)吐泡泡，氣泡在水中不斷往上冒的情況有些類似。氣泡大的（大的數(shù)據(jù)）在上面，氣泡小的（小的數(shù)據(jù)）在下面。新知講解05冒泡排序的基本原理

對(duì)存放原始數(shù)據(jù)的數(shù)組，按從前往后的方向進(jìn)行多次掃描，每次掃描稱為一趟。當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排序要求的大小次序不符合時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)行互換。新知講解05相鄰比較逆序交換把上面問(wèn)題中水桶底半徑排成從小到大的順序。原數(shù)據(jù)為：{49,38,65,97,76,13,27,49}分析：首先為了方便分析，我們把所給的數(shù)據(jù)先用一個(gè)表格列出來(lái)，如下：分析問(wèn)題06分析問(wèn)題06對(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,交換位置經(jīng)過(guò)第二趟排序，實(shí)現(xiàn)了什么目的？經(jīng)過(guò)第二趟排序，把第二大的數(shù)沉到倒數(shù)第二個(gè)位置了!9749271376654938數(shù)據(jù)87654321序號(hào)38<49,保持不變第一趟排序后的數(shù)據(jù)和序號(hào)第二趟排序的步驟：49<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分析問(wèn)題06序號(hào)12345678數(shù)據(jù)3849657613274997分析問(wèn)題06觀察原數(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ò)多少次排序呢？分析問(wèn)題，完成學(xué)習(xí)單206以小組為單位，完成學(xué)習(xí)單，寫(xiě)出完整的冒泡排序過(guò)程小組合作(8分鐘)序號(hào)12345678數(shù)據(jù)3849132749657697序號(hào)12345678數(shù)據(jù)4938659776132749序號(hào)12345678數(shù)據(jù)3849657613274997序號(hào)12345678數(shù)據(jù)3813274949657697序號(hào)12345678數(shù)據(jù)1327384949657697序號(hào)12345678數(shù)據(jù)3849651327497697序號(hào)12345678數(shù)據(jù)1327384949657697序號(hào)12345678數(shù)據(jù)1327384949657697初始1趟2趟3趟4趟5趟6趟7趟冒泡排序也可以從后往前進(jìn)行，過(guò)程演示如下：拓展07小結(jié)08相鄰元素兩兩比較、逆序交換、多輪排序冒泡排序的基本原理：冒泡排序的基本步驟：1.比較相鄰的元素2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)3.針對(duì)所有的元素重復(fù)以上的步驟，除