冒泡排序算法精选PPT.ppt

《冒泡排序算法精选PPT.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第一趟排序第一趟排序的步骤：的步骤

4、：序号序号序号序号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

5、 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

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

7、94949656565657676767613131313272727274949494997979797经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！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数据数据数据数据3838383849494949656565657676767613131313272727274949494997979

9、7974965,保持不变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数据数据数据数据38383838494949496565656576767676131313132727272749494

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

11、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不

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是是否

13、否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、按照这种画法第二趟、第三趟、第四趟排序的流程图、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？第11页，讲稿共17张，创作于星期日是是3、怎样把整个冒泡排序的流程图、怎样把整个冒泡排序的流程图画出来？画出来？开始开始结束结束j7j7j:=j:=1 1否否j:=j:

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

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

16、据数据数据数据4949494938383838656565659797979776767676131313132727272749494949我们知道经过第一趟的排序之后，最大的一个数我们知道经过第一趟的排序之后，最大的一个数已经排到最后了这样在进行第二趟排序时有没有已经排到最后了这样在进行第二趟排序时有没有必要再对第必要再对第7 7、8 8个数据再进行排序呢？个数据再进行排序呢？第14页，讲稿共17张，创作于星期日参照我们第一趟排序的画法、第二趟排序的流程图参照我们第一趟排序的画法、第二趟排序的流程图此时只需进行此时只需进行6次。次。否否是是i:=i+i:=i+1 1结束结束开始开始R1R2

17、R1=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分析：第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/10/12第17页，讲稿共17张，创作于星期日