冒泡排序ppt课件.ppt
2.3-2 2.3-2 冒泡排序冒泡排序授课人：洪伟荣授课人：洪伟荣授课班级：高一（授课班级：高一（13）班）班情景：1.观察水中的气泡往上冒的情景，气泡往上冒的时候有什么特点呢？2.第一次上体育课集队的时候体育老师是怎么样帮我们按身材的高低顺序进行排队的？冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的大的（大的数据）在下面，下面，气泡小的小的（小的数据）在上面。上面。冒泡排序的基本原理是对存放原始数据的数组，按从前往后从前往后的方向进行多次扫描多次扫描，每次扫描称为一趟。当发现相邻相邻两个数据的次序与排序要求的大小次序不符合次序不符合时，即将这两个数据进行互换进行互换。这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。做一做：下面我们请几位同学上来讲台为我们演示一下这种排序的过程，首先按照被叫到的顺序排列，再用这种方法由低到高进行排序。例：用冒泡排序的方法将下面一组无序数组例：用冒泡排序的方法将下面一组无序数组排成从小到大排成从小到大 49,38,65,97,76,13,27,49 49,38,65,97,76,13,27,49 分析：首先为了方便分析，我们把所给的数据分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：先用一个表格列出来，如下：对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？第一趟排序，一共进行了多少次比较？第一趟排序，一共进行了多少次比较？第一趟排序，一共进行了多少次比较？第一趟排序，一共进行了多少次比较？4949494927272727131313137676767697979797656565653838383849494949数据数据数据数据8 8 8 87 7 7 76 6 6 65 5 5 54 4 4 43 3 3 32 2 2 21 1 1 1序号序号序号序号4938,交换位置原数据和序号原数据和序号序序序序号号号号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数数数数据据据据4949494938383838656565659797979776767676131313132727272749494949第一趟排序第一趟排序的步骤：的步骤：序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565659797979776767676131313132727272749494949序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565659797979776767676131313132727272749494949序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565659797979776767676131313132727272749494949序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767697979797131313132727272749494949序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313979797972727272749494949序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313272727279797979749494949序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313272727274949494997979797经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！4965,保持不变6576,交换位置9713,交换位置9727,交换位置9749,交换位置经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了经过第二趟排序，把第二大的数沉到倒数第二个位置了经过第二趟排序，把第二大的数沉到倒数第二个位置了经过第二趟排序，把第二大的数沉到倒数第二个位置了!9797979749494949272727271313131376767676656565654949494938383838数据数据数据数据8 8 8 87 7 7 76 6 6 65 5 5 54 4 4 43 3 3 32 2 2 21 1 1 1序号序号序号序号3849,保持不变第一趟排序后的数据和序号第一趟排序后的数据和序号第二趟排序第二趟排序的步骤：的步骤：序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据38383838494949496565656576767676131313132727272749494949979797974965,保持不变6513,交换位置7627,交换位置7649,交换位置序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313272727274949494997979797序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313272727274949494997979797序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313272727274949494997979797序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565651313131376767676272727274949494997979797序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565651313131327272727767676764949494997979797序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据383838384949494965656565131313132727272749494949767676769797979776R2是是否否如何交换数据，这样行吗？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 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、按照这种画法第二趟、第三趟、第四趟排序的流程图、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？是是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那么现在请你对我们刚才画出的算法流程图进行优化，设计出更好的流程图避免不必要的工作。观察原数据与第一、二趟排序后的数据观察原数据与第一、二趟排序后的数据序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565657676767613131313272727274949494997979797序号序号序号序号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数据数据数据数据3838383849494949656565651313131327272727494949497676767697979797序序序序号号号号1 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 8数数数数据据据据4949494938383838656565659797979776767676131313132727272749494949我们知道经过第一趟的排序之后，最大的一个数我们知道经过第一趟的排序之后，最大的一个数已经排到最后了这样在进行第二趟排序时有没有已经排到最后了这样在进行第二趟排序时有没有必要再对第必要再对第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:=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趟？趟？针对这个问题你有什么好的方法对我们的针对这个问题你有什么好的方法对我们的算法再进行优化？算法再进行优化？选做题：设计一个算法流程图，让计算机输出九九设计一个算法流程图，让计算机输出九九乘法表。乘法表。
