冒泡排序的算法及其程序?qū)崿F(xiàn)

1、冒泡排序的算法及其程序?qū)崿F(xiàn) 教學(xué)分析：本節(jié)課是浙江教育出版社出版的普通高中課程標(biāo)準(zhǔn)實驗教科書算法與程序設(shè)計第二第3節(jié)以及第五章第3節(jié)的部分教學(xué)內(nèi)容。一組不長的數(shù)據(jù)（如5個），從小到大排序，對學(xué)生來說是一件容易的事情，但他們并不知道計算機是怎么實現(xiàn)排序的，同時他們也沒見識過計算機對大量數(shù)據(jù)（如1000個）的排序。學(xué)習(xí)排序有助于學(xué)生對計算機工作原理的認(rèn)識。冒泡排序?qū)W(xué)生來說初次接觸，但前面的枚舉算法和解析算法的部分內(nèi)容對學(xué)習(xí)排序有一定的幫助，如數(shù)組變量的定義及使用方法、雙重循環(huán)的使用方法及特點以及如何通過鍵盤輸入一批數(shù)據(jù)（即text1_keypress()事件）在前面都已涉及，冒泡排序的學(xué)習(xí)又可以

2、鞏固前面的知識。關(guān)于冒泡排序的算法及程序?qū)崿F(xiàn)我安排了3個課時，本案例是在教室內(nèi)完成的2節(jié)隨堂課，第3課時安排學(xué)生上機實踐：對鍵盤輸入的一批數(shù)據(jù)進行冒泡排序。教學(xué)目標(biāo)：1、知識與技能：了解排序及冒泡排序的概念及特點掌握冒泡排序算法的原理初步掌握冒泡排序的程序?qū)崿F(xiàn)2、過程與方法：理解冒泡排序的分析過程，并初步掌握用冒泡排序算法來設(shè)計解決簡單的排序問題3、情感態(tài)度與價值觀： 通過冒泡排序算法的分析過程，培養(yǎng)學(xué)生思維的嚴(yán)謹(jǐn)性以及用科學(xué)方法解決問題的能力使學(xué)生深入理解計算機的工作原理，激發(fā)了學(xué)生學(xué)習(xí)程序興趣。教學(xué)重點：冒泡排序算法的原理教學(xué)難點：分析冒泡排序的實現(xiàn)過程教學(xué)策略： 講授法與探究法。教師講授

3、、學(xué)生聽講，教師提問、學(xué)生動腦，層層深入，步步為營，一切水到渠成。教學(xué)準(zhǔn)備：編寫好手動輸入一批的數(shù)據(jù)的冒泡排序的程序編寫好計算機自動生成數(shù)據(jù)的冒泡排序的程序課堂中使用的教學(xué)課件教學(xué)過程：一、問題引入問題一：什么是排序？所謂排序，把雜亂無章的一列數(shù)據(jù)變?yōu)橛行虻臄?shù)據(jù),比如7，3，4，8，1這五個數(shù)據(jù)從小到大排序，結(jié)果是1，3，4，7，8，我們很容易排出來。那么電腦是怎么進行排序的呢？問題二：一批數(shù)據(jù)在VB中如何存儲的?比如如何存儲六位裁判為一位運動員評出的分?jǐn)?shù)?用數(shù)組變量來存儲一批類型、作用相同的數(shù)據(jù)，如分別用d(1),d(2),d(3),d(4),d(5),d(6)來存儲六位裁判給出的分?jǐn)?shù)。問題

4、三：如果運動員的最后得分是從這6個分?jǐn)?shù)中去掉最高分與最低分后的平均分，你認(rèn)為怎么得到？調(diào)整數(shù)組d中所有數(shù)據(jù)的存儲位置，使最小的數(shù)據(jù)存儲在d(1)中，最大的數(shù)據(jù)存儲在d(6)中，使所有數(shù)據(jù)滿足：d(1) d(2) d(3) d(4) d(5) d(6)二、冒泡排序的算法及程序?qū)崿F(xiàn)1、冒泡排序（bubble sort）的思想在一列數(shù)據(jù)中把較小的數(shù)據(jù)逐次向上推移的一種技術(shù)。冒泡排序把待排序的n個元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù)，從最下面的一個元素起，自下而上地比較相鄰的兩個元素中的數(shù)據(jù)，將較小的數(shù)據(jù)換到上面的一個元素中。重復(fù)這一過程，直到處理完最后兩個元素中的數(shù)據(jù)，稱為一遍加工。當(dāng)?shù)谝槐榧庸ね瓿蓵r

5、，最小數(shù)據(jù)已經(jīng)上升到第一個元素位置。然后對余下的n-1個元素重復(fù)上述處理過程，直至最后進行余下兩個數(shù)據(jù)的比較和交換。2、提出待排序的任務(wù)有下面一組數(shù)據(jù)，7、3、4、8、1，用冒泡法（逐次向上推移）實現(xiàn)從小到大的排序，假如這5個數(shù)據(jù)分別用數(shù)組變量a的個數(shù)組元素a(1)、a(2)、a(3)、a(4)、a(5)來存儲變量a(1) a(2) a(3) a(4) a(5)初始 7 3 4 8 1結(jié)果 1 3 4 7 83、冒泡排序的算法及程序初步實現(xiàn)（1）第一遍加工：演示：打開冒泡.swf，演示如下圖1圖1問題一：最小數(shù)據(jù)1是如何進行逐次向上推移到達(dá)第一個數(shù)據(jù)位置的，即a(1)=1？演示如下圖2：第五位

6、置（即a(5)）的1與第四位置（即a(4)）的8比較，交換；第四位置（即a(4)）的1與第三位置（即a(3)）的4比較，交換；前三位置（即a(3)）的1與第二位置（即a(2)）的3比較，交換；第二位置（即a(2)）的1與第一位置（即a(1)）的7比較，交換；圖2說明：當(dāng)?shù)谖鍌€位置的數(shù)據(jù)1從上升到第一個位置，稱為第一遍加工問題二：第一遍加工的結(jié)果？a(1)=1，a(2)a(5)為無序區(qū)域。問題三：比較了幾次？交換了幾次？比較交換的條件是什么？比較4次，交換4次，即相鄰位置的兩個數(shù)據(jù)比較，如果a(j)a(j-1)，則交換問題五：4次比較與交換，可以用VB的哪個算法模式來實現(xiàn)？如何描述For 循環(huán)+

7、If選擇for i=5 to 2 step -1 if a(i)a(i-1) then 交換next i 根據(jù)代碼解釋：最末位置的數(shù)據(jù)與前面相鄰位置的數(shù)據(jù)發(fā)生比較，如果小于前面位置的數(shù)據(jù)，則交換；重復(fù)這一過程，直到處理完第二個位置的數(shù)據(jù)與第一個位置的數(shù)據(jù)為止，完成第一遍加工問題六：比較下面兩組代碼，你認(rèn)為哪組好？為什么？for i=4 to 1 step -1 if a(i+1)a(i) then 交換next ifor i=5 to 2 step -1 if a(i)a(i-1) then 交換next i 第一組好，因為第一組更清楚表達(dá)第一遍的加工過程，也更易理解。(2)第二遍加工（邊提問

8、邊回答，邊演示，如圖3）圖3問題一：第二遍加工的數(shù)據(jù)區(qū)域為哪些？過程是怎樣的？數(shù)據(jù)區(qū)域為a(2)a(5) 的無序的區(qū)域第五個位置的8與第四位置的4發(fā)生比較，不交換；第四個位置的4與第三個位置的3比較，不交換；第三個位置的3與第二個位置的7比較，交換；完成第二遍加工（見圖3）問題二：第二遍加工的結(jié)果怎樣？實現(xiàn)的代碼如何？結(jié)果a(2)=3，a(3)a(5)是無序區(qū)域代碼如下：for i=5 to 3 step -1 if a(i)a(i-1) then 交換next i問題三：第二遍加工，比較了幾次，交換了幾次？比較了3次，交換了1次(3)第三遍加工（邊提問邊回答，邊演示，如圖4）問題一：第三遍加

9、工的結(jié)果、過程又如何？語句呢？第三遍加工的結(jié)果：a(3)=4，a(4)a(5)為無序區(qū)域第五個位置的8與第四個位置4的比較，不交換；第四個位置的4與第三個位置的7比較，交換；完成第三遍加工實現(xiàn)的語句：for i=5 to 4 step -1 if a(i)a(i-1) then 交換next i問題二：比較和交換的次數(shù)各是多少？比較了2次，交換了1次圖4(4)第四遍加工問題一：第四遍加工的結(jié)果？實現(xiàn)的代碼？第四遍加工的結(jié)果：a(4)=7，a(5)=8 實現(xiàn)的語句：for i=5 to 5 step -1 if a(i)a(i-1) then 交換next i問題二：第四遍加工比較、交換的次數(shù)各

10、多少？比較了1次，交換了0次4、5個數(shù)據(jù)冒泡排序的程序?qū)崿F(xiàn)問題一：五個數(shù)據(jù)通過冒泡排序，完成從小到大的順序，需要加工幾遍？如果是n個數(shù)據(jù)呢？4遍，n-1遍問題二：4遍加工的共同點是什么？不同點又是什么？相同點：都是重復(fù)比較（循環(huán)結(jié)構(gòu)），相同的比較方法和相同的交換條件不同點：比較與交換的次數(shù)不一樣問題三：4遍加工是否可以用雙重循環(huán)來實現(xiàn)？可以，代碼如下：for j=1 to 4 for i=5 to j+1 step -1 if a(i)a(i-1) then 交換 next inext j 說明：對于循環(huán)次數(shù)確定的循環(huán)，比如循環(huán)4次，使用For循環(huán)，循環(huán)變量的變化方式有多種表達(dá)，如For j=

11、2 to 5或者for j=4 to 7等，但我們選擇for j=1 to 4，因為它是最易理解的一種表達(dá)問題四：4遍加工一共比較了幾次？交換了幾次？ 比較的次數(shù)為：4+3+2+1=10；交換的次數(shù)為：4+1+1=65、n個數(shù)據(jù)冒泡排序的通用代碼For i=1 to n-1 for j=n to i+1 step -1 if a(j)a(j-1) then 互換next jNext i問題一：在通用代碼中，外、內(nèi)循環(huán)的條件各是什么？外循環(huán)的循環(huán)條件為：i=i+1(ji)問題二：在通用代碼中，外、內(nèi)循環(huán)的意義是什么？外循環(huán)是加工的遍數(shù)，n個數(shù)據(jù)需要加工n-1遍 內(nèi)循環(huán)是每一遍的具體加工過程問題三

12、：如何實現(xiàn)a(j)與a(j-1)的交換？使用什么語句學(xué)生回答：通過第三個變量tempTemp=A(j)A(j)=A(j-1)A(j-1)=Temp6、演示冒泡排序算法.swf，觀察流程圖，體驗流程的執(zhí)行過程，并請學(xué)生用語言表達(dá)程序運行過程三、對鍵盤輸入的一批數(shù)據(jù)進行冒泡排序1、關(guān)于程序的界面問題一：你能想象出程序的界面嗎？學(xué)生思考后并給展示如下的建議界面： 問題二：根據(jù)此界面，你能大致描述一下程序的運行過程嗎？在黃色文本框內(nèi)輸入數(shù)據(jù)后，按回車鍵，在左邊列表框list1內(nèi)顯示輸入的數(shù)據(jù)，依次輸入一批數(shù)據(jù)，然后單擊“冒泡排序”按鈕，在列表框list2中顯示已排完序的一列數(shù)據(jù)問題三：界面上有幾個對象

13、？一個窗體（form1）、二個列表框(list1、list2)、一個文本框(text1)、一個命令按鈕(command1)和三個標(biāo)簽(label1、label2、label3)問題四：在哪些對象上發(fā)生哪些事件？在text1的keypress事件和command1的click事件2、編寫事件的代碼問題一：請嘗試編寫text1_keypress（）事件的代碼Sub Text1_KeyPress(KeyAscii As Integer) If KeyAscii = 13 Then c=c+1 a(c) = Val(Text1.Text) List1.AddItem a(c) Text1.Text =

14、 : Text1.SetFocusEnd IfEnd Sub說明：text1_keyPress（）事件，在計算并聯(lián)電阻的總電阻值時已使用過，所不同的是增加了計數(shù)功能。問題二：當(dāng)在text1中用鍵盤輸入回車鍵后，做些什么內(nèi)容？ 計數(shù)（c=c+1） 給數(shù)組變量a賦值 數(shù)組變量的值在list1中顯示 text1清空，并把光標(biāo)聚焦在text1中問題三：為什么要計數(shù)？（c=c+1） 計數(shù)是為了統(tǒng)計待排序數(shù)據(jù)的個數(shù)問題四：數(shù)組變量a和變量c需要在text1_keypress()事件中定義嗎？不用，作全局性變量處理，在兩個模塊外添加如下兩行：Dim a(1 to 128) as integer Dim c

15、As Integer 說明：全局性變量的處理在計算并聯(lián)電路的總電阻中已學(xué)習(xí)過。問題五：如果要手動輸入50個待排序的數(shù)據(jù)，需要執(zhí)行text1_keypress()事件幾遍？50遍問題六：請嘗試編寫command1_click()事件Sub Command1_Click()For I = 1 To c - 1 For J = c To I + 1 Step -1 If a(J) a(J - 1) Then TEMP = a(J)：a(J) = a(J - 1)：a(J - 1) = TEMP End If Next JNext IFor I = 1 To c List2.AddItem a(I)N

16、ext IEnd Sub問題七：command1_click()事件實現(xiàn)哪幾項功能？兩項功能：一項是冒泡排序，一項是把已排好序的數(shù)組a輸出（用for循環(huán)實現(xiàn)）教師演示事先編好的程序，讓學(xué)生觀察并體驗程序的執(zhí)行過程3、關(guān)于程序的升降序功能問題一：如果要實現(xiàn)升降序的功能，界面與代碼如何修改？界面修改：添加一控件combobox，生成combo1對象Command1_click（）代碼修改如下：For I = 1 To c - 1 For J = c To I + 1 Step -1 If Combo1.Text = “升序 Then If a(J) a(J - 1) Then TEMP = a(J

17、)：a(J) = a(J - 1)：a(J - 1) = TEMP End If End If Next J Next I For I = 1 To c List2.AddItem a(I) Next I End Sub說明：else后面即為降序排序，比較的條件由原來a(J) a(J - 1)即可。添加一窗體加載模塊Sub Form_Load() Combo1.AddItem “升序 Combo1.AddItem “降序 Combo1.ListIndex = 0End Sub對三個語句稍作解釋：按下程序運行按鈕，執(zhí)行Form_load事件，在combo1中添加兩項“升序”、“降序”，界面上顯示的是升序，因為combo1.ListIndex=0教師演示事先編好的具有升降功能的程序，讓學(xué)生觀察并體驗程序的執(zhí)行過程四、關(guān)于冒泡排序的小結(jié)1、排序及冒泡排序的概念2、冒泡排序的算法思想3、n個數(shù)據(jù)冒泡排序的通用程序代碼4、用冒泡排序法對鍵盤輸入的一批數(shù)據(jù)從小到大排序的程序?qū)崿F(xiàn)變量a(1) a