冒泡排序课件.ppt

1、授课人：洪伟荣授课人：洪伟荣授课班级：高一（授课班级：高一（13）班）班情景：1.观察水中的气泡往上冒的情景，气泡往上冒的时候有什么特点呢？2.第一次上体育课集队的时候体育老师是怎么样帮我们按身材的高低顺序进行排队的？冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的大的（大的数据）在下面，下面，气泡小的小的（小的数据）在上面。上面。冒泡排序的基本原理是对存放原始数据的数组，按从前往后从前往后的方向进行多次扫描多次扫描，每次扫描称为一趟。当发现相邻相邻两个数据的次序与排序要求的大小次序不符合次序不符合时，即将这两个数据进行互换进行互换。这样，较小的数据就会逐个向前移动，好象气泡向上

2、浮起一样。做一做：下面我们请几位同学上来讲台为我们演示一下这种排序的过程，首先按照被叫到的顺序排列，再用这种方法由低到高进行排序。例：用冒泡排序的方法将下面一组无序数组例：用冒泡排序的方法将下面一组无序数组排成从小到大排成从小到大 49,38,65,97,76,13,27,49 49,38,65,97,76,13,27,49 分析：首先为了方便分析，我们把所给的数据分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：先用一个表格列出来，如下：4938,交换位置原数据和序号原数据和序号第一趟排序第一趟排序的步骤：的步骤：4965,保持不变6576,交换位置9713,交换位置9727

3、,交换位置9749,交换位置3849,保持不变第一趟排序后的数据和序号第一趟排序后的数据和序号第二趟排序第二趟排序的步骤：的步骤：4965,保持不变6513,交换位置7627,交换位置7649,交换位置76R2是是否否如何交换数据，这样行吗？R2R3是是否否t:=R2R2:=R3R3:=t不断的这样画下去要画多少个类似的选择结构？有没有办法让流程图更加简洁呢？这样交换数据，会有什么问题？分析：R1R2R1=R2是是否否t=R1R1=R2R2=t否否是是i:=i+i:=i+1 1结束结束开始开始R1R2R1=R2是是否否t=R1R1=R2R2=ti:=i:=1 1Ri i Ri i+1i i 7

4、 7t:=Ri i Ri i:=Ri i+1Ri i+1:=t分析：1.画出第一趟排序的算法流程图：用简洁的循环结构进行表示用简洁的循环结构进行表示否否是是i:=i+i:=i+1 1结束结束开始开始R1R2R1=R2是是否否t=R2R1=R2R2=ti:=i:=1 1Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:=ti i 7 7分析：后面的排序只要按照这种方法不断进行就行了。2、按照这种画法第二趟、第三趟、第四趟排序的流程图、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？怎样画？怎样把整个冒泡排序的流程图画出来？那么同样

5、的结构要进行多少次呢？有没有办法让流程图更加简洁呢？是是3、怎样把整个冒泡排序的流、怎样把整个冒泡排序的流程图画出来？程图画出来？开始开始结束结束j7j7j:=j:=1 1否否j:=j:=j j1 1是是i i 7 7否否i:=i:=1 1i:=i+i:=i+1 1是是否否Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:=t分析：这是一个两重循环结构思考交流：w在我们刚才的算法流程图中，每一趟的排序我们都进行了7次，是否每一趟的排序都需要进行7次比较呢？w那么现在请你对我们刚才画出的算法流程图进行优化，设计出更好的流程图避免不必要的工作。观察原数据与第一、二趟排序后

6、的数据观察原数据与第一、二趟排序后的数据我们知道经过第一趟的排序之后，最大的一个数我们知道经过第一趟的排序之后，最大的一个数已经排到最后了这样在进行第二趟排序时有没有已经排到最后了这样在进行第二趟排序时有没有必要再对第必要再对第7 7、8 8个数据再进行排序呢？个数据再进行排序呢？参照我们第一趟排序的画法、第二趟排序的流程图参照我们第一趟排序的画法、第二趟排序的流程图此时只需进行此时只需进行6次。次。否否是是i:=i+i:=i+1 1结束结束开始开始R1R2R1=R2是是否否t=R2R1=R2R2=ti:=i:=1 1Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:

7、=ti i 7 7否否是是i:=i+i:=i+1 1结束结束开始开始R1R2R1=R2是是否否t=R2R1=R2R2=ti:=i:=1 1Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:=ti i 6 6分析：否否是是i i j j那么我们可以把整个冒泡排序的流那么我们可以把整个冒泡排序的流程图优化成如图所示：程图优化成如图所示：开始开始结束结束否否j0j0j:=j:=7 7是是j:=j:=j-1j-1i:=i:=1 1i:=i+i:=i+1 1是是否否Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:=t分析：小结：本节课主要学习了冒泡排序的基本原理及其算法流程图，冒泡排序是最常用也是最基本的排序方法，很多其他的排序方法都可以由它改进而来，比如现在常用的快速排序法等。双循环是我们本节课刚接触的一种复杂结构，应用到本节知识的实例很多，比如：打印九九乘法口诀表、彩票数字选择器，工作表安排等等。作业：P128 A3课后思考交流：在刚才的冒泡排序中是否一定要进行在刚才的冒泡排序中是否一定要进行7趟？趟？针对这个问题你有什么好的方法对我们的针对这个问题你有什么好的方法对我们的算法再进行优化？算法再进行优化？选做题：设计一个算法流程图，让计算机输出九九设计一个算法流程图，让计算机输出九九乘法表。乘法表。