冒泡排序算法课件.ppt

《冒泡排序算法课件.ppt》由会员分享，可在线阅读，更多相关《冒泡排序算法课件.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、浮起一样。现在学习的是第3页，共17页例：用冒泡排序的方法将下面一组无序数组例：用冒泡排序的方法将下面一组无序数组排成从小到大排成从小到大 49,38,65,97,76,13,27,49 49,38,65,97,76,13,27,49 分析：首先为了方便分析，我们把所给的数据分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：先用一个表格列出来，如下：现在学习的是第4页，共17页对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？第一趟排序，一共进行了多少次比较？第

3、一趟排序，一共进行了多少次比较？第一趟排序，一共进行了多少次比较？第一趟排序，一共进行了多少次比较？49492727131376769797656538384949数据数据8 87 76 65 54 43 32 21 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

4、 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、 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数据数

6、据数据数据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数据数据数据数据38383838494949496565656

7、57676767613131313272727274949494997979797经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！4965,保持不变6576,交换位置9713,交换位置9727,交换位置9749,交换位置现在学习的是第5页，共17页经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了经过第二趟排序，把第二大的数沉到倒数第二个位置了经过第二趟排序，把第二大

8、的数沉到倒数第二个位置了经过第二趟排序，把第二大的数沉到倒数第二个位置了!97974949272713137676656549493838数据数据8 87 76 65 54 43 32 21 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,保持不变651

9、3,交换位置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序号序号

10、序号序号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

11、 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不断的这样画下去要画多少个类似的

12、选择结构？有没有办法让流程图更加简洁呢？这样交换数据，会有什么问题？分析：现在学习的是第9页，共17页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.画出第一趟排序的算法流程图：用简洁的循环结构进行表示用简洁的循环结构进行表示现在学习的是第10页，共17页否否是是i:=i+i:=i+1 1结束结束开始开始R1R2R1=R2是是否否t=R2R1=R2R2=ti:=i:=1

13、 1Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:=ti i 7 7分析：后面的排序只要按照这种方法不断进行就行了。2、按照这种画法第二趟、第三趟、第四趟排序的流程图、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？现在学习的是第11页，共17页是是3、怎样把整个冒泡排序的流程、怎样把整个冒泡排序的流程图画出来？图画出来？开始开始结束结束j7j7j:=j:=1 1否否j:=j:=j j1 1是是i i 7 7否否i:=i:=

14、1 1i:=i+i:=i+1 1是是否否Ri i Ri i+1t:=Ri i Ri i:=Ri i+1Ri i+1:=t分析：这是一个两重循环结构现在学习的是第12页，共17页思考交流：w在我们刚才的算法流程图中，每一趟的排序我们都进行了7次，是否每一趟的排序都需要进行7次比较呢？w那么现在请你对我们刚才画出的算法流程图进行优化，设计出更好的流程图避免不必要的工作。现在学习的是第13页，共17页观察原数据与第一、二趟排序后的数据观察原数据与第一、二趟排序后的数据序号序号序号序号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数据数

15、据数据数据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数据数据数据数据49494949383838386565656

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

17、 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分析：现在学习的是第15页，共17页否否是是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分析：现在学习的是第16页，共17页感感谢谢大大家家观观看看2022/9/26现在学习的是第17页，共17页