“冒泡排序算法”教案

一、教材分析

浙教版的《算法與程序設(shè)計》，在第五章第二節(jié)中對冒泡排序算法進(jìn)行了實現(xiàn)。處理教材的時候筆者將第三章提前，為第二章、第五章打下基礎(chǔ)。一是加深學(xué)生對算法與程序設(shè)計關(guān)系的體會;二是可以通過程序的實現(xiàn)加深對算法的理解。

二、學(xué)情分析

學(xué)生已經(jīng)學(xué)習(xí)過VB程序基礎(chǔ)和VB控制結(jié)構(gòu)，對簡單的分支、循環(huán)等流程有了較清楚的認(rèn)識，也實現(xiàn)過一些程序，但是對于二重循環(huán)以及循環(huán)與分支的嵌套還比較陌生。在排序算法中，對于內(nèi)外層循環(huán)的作用以及循環(huán)參數(shù)的設(shè)置可能會產(chǎn)生一些不合理或是錯誤，這需要通過實踐的體驗進(jìn)行強化理解。

三、教學(xué)目標(biāo)

知識與技能目標(biāo)：熟練掌握冒泡排序工作原理，能利用冒泡排序思想對任意給定的一個數(shù)列進(jìn)行排序，培養(yǎng)學(xué)生的動手能力。

過程與方法目標(biāo)：利用合作學(xué)習(xí)、小組探究等方式熟練理解并掌握冒泡排序算法。

情感態(tài)度與價值觀目標(biāo)：培養(yǎng)學(xué)生分析問題、發(fā)現(xiàn)規(guī)律的能力，激發(fā)學(xué)生的熱情，提升學(xué)生的信息素養(yǎng)。

四、教學(xué)重點

冒泡排序工作方式，工作原理的解析，歸納算法

五、教學(xué)難點

冒泡排序工作原理的分析，算法設(shè)計

六、教學(xué)過程

1.新課引入

第一組前五位同學(xué)分別給一張卡片，卡片上寫的是數(shù)字8、56、40、17、23。

游戲規(guī)則：從第一組第五位同學(xué)開始往前，依次與前一位學(xué)生拿到的卡片比較，如果后一位學(xué)生卡片上的數(shù)字比前一位學(xué)生的小，兩個人互換位置，直到比較到最前面一位同學(xué)為止。

其他同學(xué)觀察。

師：你們看到了什么？

生：（討論并說自己的想法。）

師：我剛才聽到同學(xué)們的發(fā)言了，最小的數(shù)在最前面了，比較了4次，交換了2次。

師：如果讓所有拿卡片的同學(xué)按照從小到大的順序就座，我們?nèi)绾翁幚砟兀科鋵崉偛诺谝唤M的五位同學(xué)就給我們展示了一種排序的方法，我們稱冒泡排序。究竟什么是排序呢？把雜亂無章的數(shù)據(jù)變?yōu)橛行驍?shù)據(jù)的過程我們稱為排序。排序在我們?nèi)粘Ｉ钪袘?yīng)用比較廣泛，比如說，每一次大型考試之后的排名，第一次體育課上的排隊等等。冒泡排序，顧名思義，形容較小的數(shù)據(jù)像水中的氣泡一樣，氣泡的質(zhì)量比水輕，往上飄。我們來一起看看剛才第一組同學(xué)在交換座位中的思路吧，我們把剛才同學(xué)的卡片按照順序存儲在數(shù)組中，數(shù)組大家還熟悉吧，在我發(fā)的導(dǎo)學(xué)案中對數(shù)組的相關(guān)知識再次介紹，不熟悉的同學(xué)可以看看。我們找一位同學(xué)上來寫一下我們第一次比較、交換的情況。

生：上臺演示剛才的處理過程。

師：課件展示排序的過程（實例分析），課件展示每一次排序結(jié)果。

觀察每一次比較次數(shù)。

2.發(fā)現(xiàn)規(guī)律

用i表示處理遍數(shù)，用j表示數(shù)組元素下標(biāo)變化

第1遍處理：i=1

d（j）lt;d（j-1）：d（5）lt;d（4）——23lt;17=1，不換23 17 40 56 8

d（j）lt;d（j-1）：d（4）lt;d（3）——17lt;40=true，換23 17 40 56 8

d（j）lt;d（j-1）：d（3）lt;d（2）——17lt;56=true，換23 40 17 56 8

d（j）lt;d（j-1）：d（2）lt;d（1）——17lt;8=1，不換23 40 56 17 8

j：5～2，比較了4次

第2遍處理：i=2

d（j）lt;d（j-1）：d（5）lt;d（4）——23lt;40=true，換23 40 56 17 8

d（j）lt;d（j-1）：d（4）lt;d（3）——23lt;56=true，換40 23 56 17 8

d（j）lt;d（j-1）：d（3）lt;d（2）——23lt;17=1，不換40 56 23 17 8

j：5～3，比較了3次

第3遍處理：i=3

d（j）lt;d（j-1）：d（5）lt;d（4）——40lt;56=true，換40 56 23 17 8

d（j）lt;d（j-1）：d（4）lt;d（3）——40lt;23=1，不換56 40 23 17 8

j：5～4，比較了2次

第4遍處理：i=4

d（j）lt;d（j-1）：d（5）lt;d（4）——56lt;40=1，不換56 40 23 17 8

j：5～5，比較了1次

3.得出結(jié)論

數(shù)組中有n個元素d（1）～d（n）時

處理遍數(shù)i：

n-1遍;i=1 To n-1

每遍比較次數(shù)：

n-i次

每遍比較時下標(biāo)j的變化：

j=n To i+1 step -1

總比較次數(shù)：

（n-1）+（n-2）+…1

n*（n-1）/2次

4.分組探究

冒泡排序算法設(shè)計（導(dǎo)學(xué)案二）

在什么情況下需要交換

生：排序的遍數(shù)用I表示，I的變化是從1到n-1

每一遍比較的次數(shù)用J表示，J的變化是從n到I+1

比較d（j）和d（j-1）之間的關(guān)系，如果d（j）lt;d（j-1），則進(jìn)行交換。

交換需要一個變量臨時存儲數(shù)據(jù)，我們用temp，這樣我們設(shè)計的算法是二重循環(huán)+選擇結(jié)構(gòu)，內(nèi)循環(huán)的循環(huán)體是選擇結(jié)構(gòu)。

師：引導(dǎo)學(xué)生歸納，學(xué)生回答結(jié)束后點評總結(jié)。

5.算法設(shè)計

二重循環(huán)+條件語句

For i=1 to n-1

For j=n to i+1 step -1

If d（j）lt;d（j-1） Then

temp=d（j）

d（j）=d（j-1）

d（j-1）=temp

End If

Next j

Next i

6.課堂拓展

如果要按照從大到小次序排序，應(yīng)如何修改冒泡算法？