3.4.1冒泡法排序算法.pptx

冒泡排序算法,宁夏西吉中学王星,可以用简图表示为图1,ACBACB图2,大家好，欢迎进入冒泡排序算法的学习！先来看这样一个问题：有两个杯子A和B，分别盛放油和醋，现要求交换两杯中的液体（即A原来盛放油，现要改为盛醋，B则相反）。请同学们思考并说出解决问题的方法和步骤？,算法(Algorithm):在计算机程序设计中我们把这种解决问题的方法和步骤称为算法。,现在，请大家在草稿纸上试着用图形，符号画出这一交换过程,也可以用字母符号简化表示为图2；,还也可以用流程图表示为图3,好，请上来一位同学给大家演示一下交换的过程,排序是日常生活中常用的算法，就是将一个无序序列变成有序序列的过程；排序的方法很多；冒泡排序是其中一种比较简而典型的算法。,通俗地讲，就是想方设法把人解决问题的思维用计算机能识别的程序设计语言（比如）表达出来，交给计算机去执行一条一条地指令从面使问题得到解决。,4个过程中，前3个过程由人完成！问题的解决最终要靠大家的聪明才智！,为何计算机有如此神奇的功能呢！请思考！,看计算机解决问题的过程:,接着来看：要将无序序列574283变成有序序列应采取（？）算法,排序,你能说出一个用排序算法解决问题的事例吗？,1、比如在Excel中我们点击“排序”按钮就能迅速而轻松完成学科成绩排名；2、再比如，有这样一款小软件运动会小组选手成绩排序，就是用冒泡排序算法实现的！,我运行后请上来一位同学做输入操作，大家来体验。,可以看到，只需点击“排序”按钮就能完成排序！,二、教学目标：知识技能目标：掌握冒泡排序的原理，能理解绘制冒泡排序算法流程图，学会编写冒泡排序程序主要代码。过程方法目标：在利用冒泡排序思想设计算法、解决排序问题的过程中培养善于分析问题，发现规律的能力；养成自顶向下，逐步细化和模块化的程序设计素养。情态价值观目标：提高学习热情，增强合作意识，体验成功设计最优方案解决问题的喜悦与幸福。三、教学重难点：重点：冒泡排序原理的理解及其流程图绘制难点：冒泡排序过程中遍、次概念的理解；规律的找寻与发现,对，本节课的任务就是解读神奇的冒泡排序原理，学会用冒泡排序算法设计、解决排序问题。,他（她）是怎么知道自己最高而排到这个位置上来的？,说说你自己是怎样排上来的？,大家认为的“看”或“本来高”其实是参与了人脑思维的飞速比较！,可计算机不像同学们一样，它看不见，摸不着，也不会思维，你们说究竟怎么个冒法：请6位同学按学号归位为大家表演冒泡排序，下面的同学做好记录找规律！（发给表格）,好，首先我们请学号为1到6的同学上来表演一下排队！（按学号1到6从左到右排成一行）,再请这6位同学按身高从低到高，从左到右排成一行,“和相邻的同学比较并交换”对，这就是冒泡排序的实质所在！是通过将相邻元素进行比较和交换，逐步将一个无序序列排列为一个有序序列。,先想象一下“冒泡”是怎样一个情景：（石头落入水中，冒起一串串泡泡；序列中大数“沉”下去，逼着小数“浮”上来靠什么“沉”和“浮”靠的是相邻两数多次，多遍“比较”、“交换”,要把6位同学的身高这个无序序列变成有序，在此思想上要领会两点：要进行多遍查找，每一遍开始总是从第1个和第2个比起，如果第1个大于第2个，则交换，否则不动；，找到一个最高的同学算一遍。多遍查找是为了找到多个相对最高的同学。每一遍又要进行多次比较，第几次就是第几个和它后面相邻的一个比，两个数比较完成算一次。多次比较是为了找到该遍相对最高的一个同学。,这次你们6人充当要排序的数据，尽量不要渗入个人看、比、换，按我们大家的冒泡想法表演看结果何如！特别强调：请同学们在排序的过程中按教师的要求做好记录，发现规律。开始与结束（“开始第一遍排序”、得到一个最大的数，“一遍结束”）怎么算一遍（得到一个大数），怎么算一次（相邻两人比较完成算一次）第一遍为何不进行第6次比较；总体为何不进行第6遍查找要结束。可逆向思考：为找到5个相对最高的同学，外层重复进行了5遍查找；里层5遍的每一遍里，为了找到该同学，相邻两同学又分别重复进行了5，4，3，2，1不同次的比较与交换，才把一个无序身高变为有序。可以看到和刚才按身高排序的结果一模一样掌声送给同学们精彩到位的表演，请回座位，谢谢表演与配合！,看记录找规律：,规律一：每一遍查找，会找到一个相对最高的同学一遍排序结束。6位同学按冒泡的思想进行了（）遍查找变无序的身高为有序。n位呢？（）,若用：i：记录正在执行的排序的遍数；n:记录参与排序的总个数请同学们试着写出二者的关系！,56-1,n-1,遍数个数1（i=n-1）：,可以理解为n个无序的数，若想变它为有序，则需要进行n-1遍冒泡排序。,反过来可以把i=n-1作为控制是否冒泡排序的条件，若遍数小于等于，继续进行查找，否则已变为有序结束查找。,可以理解为每遍要比较多少次，要看是第几遍，比如第一遍n=6,i=1,所以最多比较j=6-1次,规律二：看你记录的表，为找到第i个相对最高的同学，第i遍要比较多少次？,反过来可以用j=n-i作为控制第i遍是否还进行比较的条件，若本遍比较次数j小于总数减遍数则继续本遍多次比较，否则进行下一遍查找的比较,规律三：3.如果用一数组a来存放参与冒泡排序的数，则每次是a(j)和a(j+1)相邻两数比较。,次数总数遍数（j=n-i）,请同学们试着写出三者的关系:,就是为了直观描述冒泡排序算法，用流程图来表示。,先回顾，再绘图,1.流程图（FlowChart）:是对算法形象、直观的图形化表示。通俗地讲：就是用一系列代表特殊含义的图形符号勾勒出解决问题的思路来。,看图例：,前面是用自然语言表述冒泡排序算法，你们能把排队用图形，符号表示出来,2.程序设计的三大结构和对应的可用语句,ifendif,fornext,现用动画来逼真演示执行过程：,一同来回顾理解,好，下面类比排队，在试探中画出冒泡排序流程图（一组一图；完成交互检查；分组平台展示，对比原图修改完善）,开始,结束,大数不断的“下沉”，小数不断的“浮起”（被逼起）（不断找到最高的同学）,流程图1,开始,结束,冒泡排序（排队）,粗略的总流程图,同学们动一下脑筋看能把“冒泡排序”模块用形象的语言地表述出来吗,思考：总体看：我们在做什么？（冒泡排序！排队）请粗略画出总流程图,原来就这么简单！,“不断”有没有个终了！（有），其实质是个什么结构？（循环）谁来控制这个终了？（遍数i）,开始,结束,一遍“沉”下一个大数（一遍“找到”一个最高的同学）,流程图,分析：（1）是什么结构（因为反复进行了5遍查找，所以实质上是一个5遍循环）（2）由谁来控制循环，循环条件是什么（因为是遍数的循环，所以由遍数i来控制，当i5时不再循环）（3）由哪些基本框图组成（循环结构的基本组成是菱形框和矩形框）,？“找”了几遍（5）怎么用图描述,5,但这个图好像不够规范！循环结构不是这样子的！，想一想用较规范的循环结构图表示。,流程图3（6个数进行了6-1遍查找流程图）,开始,结束,i=1,沉下一个大数（找到一个最高的同学）,i=i+1,Y,N,i=6-1,细化一：外层循环图,如果参与排序的数是n个呢？（把流程图3中的6-1变为n-1即可！）,再进一步细化:请同学们把模块“找到一个同学”用流程图表示出来。,流程图,流程图3（6个数进行了6-1遍查找流程图）,开始,结束,i=1,沉下一个大数（找到一个最高的同学）,i=i+1,Y,N,id(j+1)then内层条件判断开始K=d(j):d(j)=d(j+1):d(j+1)=k循环体（赋值操作）endif内层条件判断结束nextj内层多次比较循环结束Nexti外层多遍循环结束,1.算法2.排序3.计算机解问题的过程4.冒泡排序算法的原理5.冒泡排序算法流程图6.流程图到程序设计语言的转换,四、小结：,请同学们小结本节课,1、尝试把总流程图转换成VB程序设计语言（为下节上机调试程序作准备）2、设计一个评分流程图，6个评委，最后得分为去掉最高分和最低分的平均分。,五、作业与练习,练习：对无序序列：574283用冒泡排序的思想完成填表。（引导）填写表一到表六：1.按顺序一组一表2.组间交换检查填表结果3.展示给大家（填表片刻后展示前教师给出第一遍排序）4.教师给出整体一次完成排序示范（出示课题）5.对比教师所给修改所填表格,六、质疑拓展优化,现在，同学们对冒泡排序的整个过程有什么问题，可以大胆的提出来我们共同思考解答！,5.学以致用：你怎么知道冒泡排序原理的，教师是怎样画出流程图的！,1.对于无序序列574283的排序有必要这样花一节课烦人吗，一眼就可