冒泡排序

第9章排序算法——冒泡排序情景：观察水中的气泡往上冒的情景，有什么特点呢？冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的（大的数据）在下面，气泡小的（小的数据）在上面。冒泡排序的基本原理对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。例：用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。{49,38,65,97,76,13,27,49}分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：对比原数据经过第一趟排序，实现了什么目的？第一趟排序，一共进行了多少次比较？4927137697653849数据87654321序号4938,交换位置原数据和序号序号12345678数据4938659776132749第一趟排序的步骤：序号12345678数据3849659776132749序号12345678数据3849659776132749序号12345678数据3849659776132749序号12345678数据3849657697132749序号12345678数据3849657613972749序号12345678数据3849657613279749序号12345678数据3849657613274997经过第一趟排序，把最大的数沉到最底了！4965,保持不变6597,保持不变9776,交换位置9713,交换位置9727,交换位置9749,交换位置经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了!9749271376654938数据87654321序号3849,保持不变第一趟排序后的数据和序号第二趟排序的步骤：序号12345678数据38496576132749974965,保持不变6576,保持不变7613,交换位置7627,交换位置7649,交换位置序号12345678数据3849657613274997序号12345678数据3849657613274997序号12345678数据3849657613274997序号12345678数据3849651376274997序号12345678数据3849651327764997序号12345678数据38496513274976977697,保持不变序号12345678数据3849651327497697观察原数据与第一、二趟排序后的数据序号12345678数据3849657613274997序号12345678数据3849651327497697序号12345678数据4938659776132749问：为了使这一组无序数组完全按照要求排成从小到大我们还需不需要再继续排序呢？问：那么我们预计最多一共要经过多少次排序呢？序号12345678数据3849132749657697序号12345678数据4938659776132749序号12345678数据3849657613274997序号12345678数据3813274949657697序号12345678数据1327384949657697序号12345678数据3849651327497697序号12345678数据1327384949657697序号12345678数据1327384949657697初始1趟2趟3趟4趟5趟6趟7趟例题：下面我们继续考虑，将我们刚才排序的全过程用算法流程图表示出来。我们把它分成几步来做，第一步，先把第一趟的排序用流程图描述出来。R[1]:=R[2]t:=R[1]R[1]:=R[2]R[2]:=t开始1.画出第一趟排序的算法流程图：假设该数据列为R[1],R[2],R[3],R[4],R[5],R[6],R[7],R[8]第一步做什么？R[1]R[2]是否如何交换数据，这样行吗？R[2]R[3]是否t:=R[2]R[2]:=R[3]R[3]:=t…不断的这样画下去要画多少个类似的选择结构？有没有办法让流程图更加简洁呢？这样交换数据，会有什么问题？分析：R[1]R[2]R[1]=R[2]是否t=R[1]R[1]=R[2]R[2]=t否是i:=i+1结束开始R[1]R[2]R[1]=R[2]是否t=R[1]R[1]=R[2]R[2]=ti:=1R[i]R[i+1]i7t:=R[i]R[i]:=R[i+1]R[i+1]:=t分析：1.画出第一趟排序的算法流程图：用简洁的循环结构进行表示否是i:=i+1结束开始R[1]R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=ti:=1R[i]R[i+1]t:=R[i]R[i]:=R[i+1]R[i+1]:=ti7分析：后面的排序只要按照这种方法不断进行就行了。2、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？是3、怎样把整个冒泡排序的流程图画出来？开始结束j7j:=1否j:=j＋1是i7否i:=1i:=i+1是否R[i]R[i+1]t:=R[i]R[i]:=R[i+1]R[i+1]:=t分析：这是一个两重循环结构课堂思考：在我们刚才的算法流程图中，每一趟的排序我们都进行了7次，是否每一趟的排序都需要进行7次比较呢？观察原数据与第一、二趟排序后的数据序号12345678数据3849657613274997序号12345678数据3849651327497697序号12345678数据4938659776132749我们知道经过第一趟的排序之后，最大的一个数已经排到最后了这样在进行第二趟排序时有没有必要再对第7、8个数据再进行排序呢？扩展:1234’322964783445冒泡排序也可以从后往前进行，过程演示如下：小结：本节课主要学习了冒泡排序的基本原理及其算法流程图。其中数组和双循环是我们本节课使用较多的一种结构。应用到本节知识的实例有很多，比如：打印九九乘法口诀表、彩票数字选择器、工作表安排等等。课后作业：在刚才的冒泡排序中是否一定要进行7趟？针对这个问题你有什么好的方法对我们的算法再进行优化？下课了。。。休息一会儿。。。一、说课题课题名称：冒泡排序选用教材：《数据结构》西安交通大学出版社适用范围：计算机及相关专业课题位置：第9章排序冒泡排序二、说对课题的分析与处理1、地位作用2、目标要求3、重点难点排序的方法设计中包含的丰富的程序设计技巧，这对初学者提高软件设计能力帮助很大。而且本知识点也是后续学习“查找”的一个基础。（1）认知方面：掌握冒泡排序的原理和流程图；（2）技能方面：掌握冒泡排序的优化方法；（3）情感方面：培养学习乐趣和解决实际问题应用的能力。（1）重点：冒泡排序的原理；（2）难点：冒泡排序的优化方法。三、教学对象分析1、本课题教学对象2、学生特点教育技术学专业本科大二学生（1）具备计算机的基础知识；（2）具备基本的C程序的阅读能力；（3）但是较计算机专业的学生来说，动手和独立思考的能力教差。四、说教学策略1、教学方法2、学法指导（1）讲解法——帮助学生理解较为抽象的课堂知识（2）举例法——通过举例，深入理解理论知识（3）讨论法——针对课堂问题，讨论优化算法的策略（4）情景教学法倡导“自主、合作、探究”的学习方式，具体的学法是讨论法。五、说讲授程序1、新课导入结合之前学习的有关排序的概念、数组的概念以及循环算法的概念，并采用情景教学的方法，引入冒泡排序的基本原理。这样导课比较形象、生动，调动学生学习的积极性。2、内容讲解（1）冒泡的基本原理采用情景教学和实例教学相结合的方法（2）冒泡的流程图主要采用讲解法（3）冒泡的算法优化问题主要采用课堂讨论和提问的方式（4）冒泡的知识点扩展采用课堂演示的方法（5）小结在讲解的冒泡排序算法的基础上，思考进一步的优化算法。加深学生对知识的掌握和理解。3、作业布置