冒泡排序的算法及其程序实现

1、冒泡排序的算法及其程序实现教学分析：本节课是浙江教育出版社出版的普通高中课程标准实验教科书算法与程序设计第二第 3 节以及第五章第 3节的部分教学内容。一组不长的数据(如 5 个)，从小到大排序，对学生来说是一件容易的事情，但他们并不知道计算机是怎么实现排序的，同时他们也没见识过计算机对大量数据(如 1000 个)的排序。学习排序有助于学生对计算机工作原理的认识。冒泡排序对学生来说初次接触，但前面的枚举算法和解析算法的部分内容对学习排序有一定的帮助，如数组变量的定义及使用方法、双重循环的使用方法及特点以及如何通过键盘输入一批数据(即 text1_keypress()事件)在前面都已涉及，冒泡排

2、序的学习又可以巩固前面的知识。关于冒泡排序的算法及程序实现我安排了 3 个课时，本案例是在教室内完成的 2 节随堂课，第 3 课时安排学生上机实践：对键盘输入的一批数据进行冒泡排序。教学目标：1、知识与技能：了解排序及冒泡排序的概念及特点掌握冒泡排序算法的原理初步掌握冒泡排序的程序实现2、过程与方法：理解冒泡排序的分析过程，并初步掌握用冒泡排序算法来设计解决简单的排序问题3、情感态度与价值观：通过冒泡排序算法的分析过程，培养学生思维的严谨性以及用科学方法解决问题的能力使学生深入理解计算机的工作原理，激发了学生学习程序兴趣。教学重点：冒泡排序算法的原理教学难点：分析冒泡排序的实现过程教学策略：讲

3、授法与探究法。教师讲授、学生听讲，教师提问、学生动脑，层层深入，步步为营，一切水到渠成。教学准备：编写好手动输入一批的数据的冒泡排序的程序编写好计算机自动生成数据的冒泡排序的程序课堂中使用的教学课件教学过程：一、问题引入问题一：什么是排序？所谓排序，把杂乱无章的一列数据变为有序的数据，比如 7,3,4,8,1 这五个数据从小到大排序，结果是 1,3,4,7,8,我们很容易排出来。那么电脑是怎么进行排序的呢？问题二：一批数据在 VB 中如何存储的？比如如何存储六位裁判为一位运动员评出的分数？用数组变量来存储一批类型、作用相同的数据，如分别用 d(1),d(2),d(3),d(4),d(5),d(

4、6)来存储六位裁判给出的分数。问题三：如果运动员的最后得分是从这 6 个分数中去掉最高分与最低分后的平均分，你认为怎么得到？调整数组 d 中所有数据的存储位置，使最小的数据存储在 d(1)中，最大的数据存储在d(6)中，使所有数据满足：d(1)d(2)d(3)d(4)d(5)d(6)二、冒泡排序的算法及程序实现1 1、冒泡排序(bubblesort)bubblesort)的思想在一列数据中把较小的数据逐次向上推移的一种技术。冒泡排序把待排序的 n 个元素的数组看成是垂直堆放的一列数据，从最下面的一个元素起，自下而上地比较相邻的两个元素中的数据，将较小的数据换到上面的一个元素中。重复这一过程，直

5、到处理完最后两个元素中的数据，称为一遍加工。当第一遍加工完成时，最小数据已经上升到第一个元素位置。然后对余下的 n-1 个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。2 2、提出待排序的任务有下面一组数据，7、3、4、8、1,用冒泡法(逐次向上推移)实现从小到大的排序，假如这 5 个数据分别用数组变量 a 的5个数组元素 a(1)、a(2)、a(3)、a(4)、a(5)来存储变量a(1)a(2)a(3)a(4)a(5)初始73481结果134783 3、冒泡排序的算法及程序初步实现(1)第一遍加工：演示：打开冒泡.swf,演示如下图 1问题一：最小数据 1 是如何进行逐次向上推

6、移到达第一个数据位置的，即 a(1)=1?演示如下图 2：第五位置(即 a(5)的 1 与第四位置(即第四位置(即 a(4)的 1 与第三位置(即前三位置(即 a(3)的 1 与第二位置(即第二位置(即 a(2)的 1 与第一位置(即a(4)的 8 比较，交换;a(3)的 4 比较，交换;a(2)的 3 比较，交换;a(1)的 7 比较，交换;图 1图 2说明：当第五个位置的数据 1 从上升到第一个位置，称为第一遍加工问题二：第一遍加工的结果？a(1)=1,a(2)a(5)为无序区域。问题三：比较了几次？交换了几次？比较交换的条件是什么？比较 4 次，交换 4 次，即相邻位置的两个数据比较，如

7、果 a(j)a(j-1),则交换问题五：4 次比较与交换，可以用 VB 的哪个算法模式来实现？如何描述For 循环+If 选择fori=5to2step-1ifa(i)a(i-1)then交换nexti根据代码解释：最末位置的数据与前面相邻位置的数据发生比较，如果小于前面位置的数据,则交换；重复这一过程，直到处理完第二个位置的数据与第一个位置的数据为止，完成第遍加工问题六：比较下面两组代码，你认为哪组好？为什么？第一组好，因为第一组更清楚表达第一遍的加工过程，也更易理解。fori=5to2step-1ifa(i)a(i-1)then交换nextifori=4to1step-1ifa(i+1)a

8、(i)then交换nexti(2)第二遍加工(边提问边回答，边演示，如图3)图 3问题一：第二遍加工的数据区域为哪些？过程是怎样的？数据区域为 a(2)a(5)的无序的区域第五个位置的 8 与第四位置的 4 发生比较，不交换；第四个位置的 4 与第三个位置的 3 比较，不交换；第三个位置的 3 与第二个位置的 7 比较，交换；完成第二遍加工(见图 3)问题二：第二遍加工的结果怎样？实现的代码如何？结果 a(2)=3,a(3)a(5)是无序区域代码如下:fori=5to3step-1ifa(i)a(i-1)then交换nexti问题三：第二遍加工，比较了几次，交换了几次？比较了 3 次，交换了

9、1 次(3)第三遍加工(边提问边回答，边演示，如图 4)问题一：第三遍加工的结果、过程又如何？语句呢？第三遍加工的结果：a(3)=4,a(4)a(5)为无序区域第五个位置的 8 与第四个位置 4 的比较，不交换；第四个位置的 4 与第三个位置的 7比较，交换；完成第三遍加工实现的语句：fori=5to4step-1ifa(i)a(i-1)then交换nexti问题二：比较和交换的次数各是多少?比较了 2 次，交换了 1 次图 4(4)第四遍加工问题一：第四遍加工的结果？实现的代码？第四遍加工的结果：a(4)=7,a(5)=8实现的语句：fori=5to5step-1ifa(i)a(i-1)th

10、en交换nexti问题二：第四遍加工比较、交换的次数各多少？比较了 1 次，交换了 0 次4 4、5 5 个数据冒泡排序的程序实现问题一：五个数据通过冒泡排序，完成从小到大的顺序，需要加工几遍？如果是 n 个数据呢?4 遍，n-1 遍问题二：4 遍加工的共同点是什么？不同点又是什么？相同点：都是重复比较(循环结构)，相同的比较方法和相同的交换条件不同点：比较与交换的次数不一样问题三：4 遍加工是否可以用双重循环来实现?可以，代码如下：forj=1to4fori=5toj+1step-1ifa(i)a(i-1)then交换nextinextj说明：对于循环次数确定的循环，比如循环 4 次，使用

11、For 循环，循环变量的变化方式有多种表达，如 Forj=2to5 或者 forj=4to7 等，但我们选择 forj=1to4,因为它是最易理解的一种表达问题四：4 遍加工一共比较了几次？交换了几次？比较的次数为：4+3+2+1=10;交换的次数为：4+1+1=65 5、n n 个数据冒泡排序的通用代码Fori=1ton-1forj=ntoi+1step-1ifa(j)a(j-1)then 互换nextjNexti问题一：在通用代码中，外、内循环的条件各是什么？外循环的循环条件为：i=i+1(ji)问题二：在通用代码中，外、内循环的意义是什么？外循环是加工的遍数，n 个数据需要加工 n-1

12、遍内循环是每一遍的具体加工过程问题三：如何实现 a(j)与 a(j-1)的交换？使用什么语句学生回答：通过第三个变量 tempTemp=A(j)A(j)=A(j-1)A(j-1)=Temp6 6、演示冒泡排序算法.swf,.swf,观察流程图，体验流程的执行过程，并请学生用语言表达程序运行过程曾法与程庠过廿$1i$1i 助筋iWniWn1?1?叫卜4-1)4-1)H H 始三、对键盘输入的一批数据进行冒泡排序1 1、关于程序的界面学生思考后并给展示如下的建议界面:瑜由己田厅的数却总电财逵杼华东师范大学出应社i,耳换雨)与取的数据问题二：根据此界面，你能大致描述一下程序的运行过程吗？在黄色文本框

13、内输入数据后，按回车键，在左边列表框 listl 内显示输入的数据，依次输入一批数据，然后单击“冒泡排序”按钮，在列表框 list2 中显示已排完序的一列数据问题三：界面上有几个对象？一个窗体（forml）、二个列表框（listl、list2）、一个文本框（textl）、一个命令按钮（commandl）和三个标签（labell、label2、label3）问题四：在哪些对象上发生哪些事件？在 textl 的 keypress 事件和 commandl 的 click 事件2 2、编写事件的代码问题一：请尝试编写 text1_keypress（）事件的代码SubText1_KeyPress(Ke

14、yAsciiAsInteger)IfKeyAscii=13Thenc=c+1a(c)=Val(Text1.Text)List1.AddItema(c)Text1.Text=:Text1.SetFocusEndIftext1_keyPress（）事件，在计算并联电阻的总电阻值时已使用过,所不同的是增加了计数功能。问题二：当在 text1 中用键盘输入回车键后，做些什么内容?计数（c=c+1）给数组变量 a 赋值数组变量的值在 list1 中显示text1 清空，并把光标聚焦在 text1 中问题三：为什么要计数？（c=c+1）计数是为了统计待排序数据的个数问题四：数组变量 a 和变量 c 需要在

15、 text1_keypress（）事件中定义吗?不用，作全局性变量处理，在两个模块外添加如下两行：Dima(1to128)asintegerDimcAsInteger 说明：全局性变量的处理在计算并联电路的总电阻中已学习过。问题五：如果要手动输入 50 个待排序的数据，需要执行 text1_keypress()事件几遍?50 遍问题六：请尝试编写 command1_click()事件说明SubCommand1_Click()ForI=1Toc-1ForJ=cToI+1Step-1Ifa(J)a(J-1)ThenTEMP=a(J):a(J)=a(J-1):a(J-1)=TEMPEndIfNext

16、JNextIForI=1TocList2.AddItema(I)NextIEndSub 问题七：command1_click()事件实现哪几项功能？两项功能：一项是冒泡排序，一项是把已排好序的数组 a 输出(用 for 循环实现)教师演示事先编好的程序，让学生观察并体验程序的执行过程3 3、关于程序的升降序功能问题一：如果要实现升降序的功能，界面与代码如何修改？界面修改：添加一控件 combobox,生成 combo1 对象Command1_click()代码修改如下：ForI=1Toc-1ForJ=cToI+1Step-1IfCombo1.Text=升序ThenIfa(J)a(J-1)The

17、nTEMP=a(J):a(J)=a(J-1):a(J-1)=TEMPEndIfEndIfNextJNextIForI=1TocList2.AddItema(I)NextIEndSub说明：else 后面即为降序排序，比较的条件由原来 a(J)a(J-1)即可。添加一窗体加载模块SubForm_Load()Combol.AddItem升序Combol.AddItem降序Combol.ListIndex=0EndSub对三个语句稍作解释：按下程序运行按钮，执行 Form_load 事件，在 combo1 中添加两项“升序、降序，界面上显示的是升序，因为 combo1.ListIndex=0教师演示事先编好的具有升降功能的程序，让学生观察并体验程序的执行过程四、关于冒泡排序的小结1、排序及冒泡排序的概念2、冒泡排序的算法思想3、n 个数