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

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

2、前面都已涉及，冒泡排序的學(xué)習(xí)又可以鞏固前面的知識。關(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é)生思維的嚴謹性以及用科學(xué)方法解決問題的能力 使學(xué)生深入理解計算機的工作原理，激發(fā)了學(xué)生學(xué)習(xí)程序興趣。教學(xué)重點：冒泡排序算法的原理教學(xué)難點：分析冒

3、泡排序的實現(xiàn)過程教學(xué)策略：講授法與探究法。教師講授、學(xué)生聽講，教師提問、學(xué)生動腦，層層深入，步步為營， 一切水到渠成。教學(xué)準備：編寫好手動輸入一批的數(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 中如何存儲的 ?比如如何存儲六位裁判為一位運動員評出的分數(shù)?用數(shù)組變量來存儲一批類型、 作用相同的數(shù)據(jù)， 如分別用 d(1),d

4、(2),d(3),d(4),d(5),d(6) 來存 儲六位裁判給出的分數(shù)。問題三：如果運動員的最后得分是從這 6 個分數(shù)中去掉最高分與最低分后的平均分， 你認為怎么得到？調(diào)整數(shù)組d中所有數(shù)據(jù)的存儲位置，使最小的數(shù)據(jù)存儲在d(1)中，最大的數(shù)據(jù)存儲在d(6)中，使所有數(shù)據(jù)滿足：d(1) < d(2) w d(3) < d(4) < d(5) < d(6)二、冒泡排序的算法及程序?qū)崿F(xiàn)1 冒泡排序(bubble sort)的思想在一列數(shù)據(jù)中把較小的數(shù)據(jù)逐次向上推移的一種技術(shù)。冒泡排序把待排序的n個元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù)，從最下面的一個元素起，自下而上地比較相鄰的

5、兩個元素中的數(shù)據(jù)，將較小的數(shù)據(jù)換到上面的一個元素中。重復(fù)這一過程，直到處理完最后兩個元素中的數(shù)據(jù)，稱為一遍加工。當(dāng)?shù)谝槐榧庸ね瓿蓵r，最小數(shù)據(jù)已經(jīng)上升到第一個元素位置。然后對余下的n-1個元素重復(fù)上述處理過程，直至最后進行余下兩個數(shù)據(jù)的比較和交換。2、提出待排序的任務(wù)有下面一組數(shù)據(jù)，7、3、4、& 1,用冒泡法(逐次向上推移)實現(xiàn)從小到大的排序， 假如這5個數(shù)據(jù)分別用數(shù)組變量 a的5個數(shù)組元素a(1)、a(2)、a(3)、a(4)、a(5)來存儲變量a(1)a(2)a(3)a(4)a(5)初始73481結(jié)果134783、冒泡排序的算法及程序初步實現(xiàn)(1)第一遍加工：演示：打開冒泡.swf

6、,演示如下圖1圖1a(4)的8比較，交換; a(3)的4比較，交換; a(2)的3比較，交換; a(1)的7比較，交換;問題一：最小數(shù)據(jù)1是如何進行逐次向上推移到達第一個數(shù)據(jù)位置的，即a(1)=1 ?演示如下圖2：第五位置(即a(5)的1與第四位置(即第四位置(即a(4)的1與第三位置(即前三位置(即a(3)的1與第二位置(即第二位置(即a(2)的1與第一位置(即圖2說明：當(dāng)?shù)谖鍌€位置的數(shù)據(jù)1從上升到第一個位置，稱為第一遍加工問題二：第一遍加工的結(jié)果？a(1)=1，a(2)a(5)為無序區(qū)域。問題三：比較了幾次？交換了幾次？比較交換的條件是什么？比較4次，交換4次，即相鄰位置的兩個數(shù)據(jù)比較，如

7、果 a(j)<a(j-1)，則交換問題五：4次比較與交換，可以用VB的哪個算法模式來實現(xiàn)？如何描述For循環(huán)+lf選擇for i=5 to 2 step -1 if a(i)<a(i-1) then 交換n ext i根據(jù)代碼解釋：最末位置的數(shù)據(jù)與前面相鄰位置的數(shù)據(jù)發(fā)生比較，如果小于前面位置的數(shù)據(jù),則交換；重復(fù)這一過程，直到處理完第二個位置的數(shù)據(jù)與第一個位置的數(shù)據(jù)為止，完成第遍加工問題六：比較下面兩組代碼，你認為哪組好？為什么？for i=5 to 2 step -1for i=4 to 1 step -1if a(i)<a(i-1) the n 交換if a(i+1)<

8、;a(i) then 交換n ext inext i第一組好，因為第一組更清楚表達第一遍的加工過程，也更易理解。第二遍加工(邊提問邊回答，邊演示，如圖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 -1if a(i)<a(i-1) the n交

9、換next i問題三：第二遍加工，比較了幾次，交換了幾次？比較了 3次，交換了 1次第三遍加工(邊提問邊回答，邊演示，如圖4)問題一：第三遍加工的結(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) the n交換n ext i問題二：比較和交換的次數(shù)各是多少? 比較了 2次，交換了 1次圖4第四遍加工問題一：第四遍加工的結(jié)果？實現(xiàn)的代碼？ 第四遍加工的結(jié)果：a(4)=

10、7, a(5)=8 實現(xiàn)的語句：for i=5 to 5 step -1if a(i)<a(i-1) the n 交換 n ext i問題二：第四遍加工比較、交換的次數(shù)各多少? 比較了 1次，交換了 o次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 4for i=5 to j+1 ste

11、p -1 if a(i)<a(i-1) then 交換 next inext j說明：對于循環(huán)次數(shù)確定的循環(huán)，比如循環(huán)4次，使用For循環(huán)，循環(huán)變量的變化方式有多種表達，如For j=2 to 5或者for j=4 to 7等，但我們選擇for j=1 to 4，因為它是最易理解的 一種表達問題四：4遍加工一共比較了幾次？交換了幾次？比較的次數(shù)為：4+3+2+1=10 ;交換的次數(shù)為：4+1+1=65、n個數(shù)據(jù)冒泡排序的通用代碼For i=1 to n-1for j=n to i+1 step -1 if a(j)<a(j-1) the n互換n ext jNext i問題一：在通

12、用代碼中，外、內(nèi)循環(huán)的條件各是什么？外循環(huán)的循環(huán)條件為：i<=n-1 ;內(nèi)循環(huán)的循環(huán)條件為：j>=i+1(j>i) 問題二：在通用代碼中，外、內(nèi)循環(huán)的意義是什么？外循環(huán)是加工的遍數(shù)，n個數(shù)據(jù)需要加工 n-1遍內(nèi)循環(huán)是每一遍的具體加工過程問題三：如何實現(xiàn) a(j)與a(j-1)的交換？使用什么語句<j)*珀書學(xué)生回答：通過第三個變量tempTemp=A(j)A(j)=A(j-1)A(j-1)=Temptemp6、演示冒泡排序算法.swf，觀察流程圖，體驗流程的執(zhí)行過程，并請學(xué)生用語言表達程序 運行過程三、對鍵盤輸入的一批數(shù)據(jù)進行冒泡排序1關(guān)于程序的界面問題一：你能想象出程

13、序的界面嗎？學(xué)生思考后并給展示如下的建議界面：問題二：根據(jù)此界面，你能大致描述一下程序的運行過程嗎？在黃色文本框內(nèi)輸入數(shù)據(jù)后，按回車鍵，在左邊列表框listl內(nèi)顯示輸入的數(shù)據(jù)，依次輸入一批數(shù)據(jù)，然后單擊“冒泡排序”按鈕，在列表框list2中顯示已排完序的一列數(shù)據(jù)問題三：界面上有幾個對象？一個窗體（forml ）、二個列表框（listl、list2）、一個文本框（textl）、一個命令按鈕（commandl） 和三個標(biāo)簽（labell、label2、Iabel3）問題四：在哪些對象上發(fā)生哪些事件？在 textl 的 keypress事件和 commandl 的 click 事件2、編寫事件的代碼

14、問題一：請嘗試編寫 text1_keypress （）事件的代碼Sub Text1_KeyPress(KeyAscii As Integer)If KeyAscii = 13 Thenc=c+1a(c) = Val(Text1.Text)List1.Addltem a(c)說明Text1.Text = "": Text1.SetFocus問題二：當(dāng)在text1中用鍵盤輸入回車鍵后，做些什么內(nèi)容?計數(shù)（c=c+1）給數(shù)組變量a賦值數(shù)組變量的值在list1中顯示text1清空，并把光標(biāo)聚焦在text1中問題三：為什么要計數(shù)？（C-C+1 ）End Iftext1_keyPres

15、s （） 事件，在計算并聯(lián)電阻的總電阻值時已使用過，所不同的是增加了計數(shù)功能。計數(shù)是為了統(tǒng)計待排序數(shù)據(jù)的個數(shù)問題四：數(shù)組變量 a和變量c需要在text1_keypress（）事件中定義嗎? 不用，作全局性變量處理，在兩個模塊外添加如下兩行：Dim a(1 to 128) as in tegerDim c As In teger 說明：全局性變量的處理在計算并聯(lián)電路的總電阻中已學(xué)習(xí)過。問題五：如果要手動輸入50個待排序的數(shù)據(jù)，需要執(zhí)行text1_keypress()事件幾遍?50遍問題六：請嘗試編寫command1_click()事件Sub Comma nd1_Click()For I = 1

16、To c - 1For J = c To I + 1 Step -1If a(J) < a(J - 1) ThenTEMP = a(J) : a(J) = a(J - 1) : a(J - 1) = TEMPEnd IfNext JNext IFor I = 1 To cList2.Addltem a(I)Next IEnd Sub問題七：command1_click()事件實現(xiàn)哪幾項功能？兩項功能：一項是冒泡排序，一項是把已排好序的數(shù)組a輸出(用for循環(huán)實現(xiàn))教師演示事先編好的程序，讓學(xué)生觀察并體驗程序的執(zhí)行過程 3、關(guān)于程序的升降序功能 問題一：如果要實現(xiàn)升降序的功能，界面與代碼如

17、何修改？ 界面修改：添加一控件combobox，生成combo1對象 Command1_click ()代碼修改如下：For I = 1 To c - 1For J = c To I + 1 Step -1If Combo1.Text = 升序"ThenIf a(J) < a(J - 1) The nTEMP = a(J) : a(J) = a(J - 1) : a(J - 1) = TEMP End IfElseIf a(J) > a(J - 1) The nTEMP = a(J) : a(J) = a(J - 1) : a(J - 1) = TEMP End IfEn

18、d IfNext JNext IFor I = 1 To cList2.AddItem a(I)Next IEnd Sub 說明：else后面即為降序排序，比較的條件由原來 a(J) < a(J - 1)改為a(J) >a(J - 1)即可。添加一窗體加載模塊Sub Form_Load()Combol.Addltem “ 升序”Combol.Addltem “ 降序” Combol.List In dex = 0End Sub對三個語句稍作解釋： 按下程序運行按鈕，執(zhí)行Form_load事件，在combo1中添加兩項"升 序”"降序"，界面上顯示的是升序，因為combo1 .ListIndex=0教師演示事先編好的具有升降功能的程序，讓學(xué)生觀察并體驗程序的執(zhí)行過程四、關(guān)于冒泡排序的小結(jié)1、排序及冒泡排序的概念2、冒泡排序