冒泡排序算法PPT课件.ppt
关于冒泡排序算法第一张，PPT共十七页，创作于2022年6月情景：1.观察水中的气泡往上冒的情景，气泡往上冒的时候有什么特点呢？2.第一次上体育课集队的时候体育老师是怎么样帮我们按身材的高低顺序进行排队的？第二张，PPT共十七页，创作于2022年6月冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的大的（大的数据）在下面，下面，气泡小的小的（小的数据）在上面。上面。冒泡排序的基本原理是对存放原始数据的数组，按从前往后从前往后的方向进行多次扫描多次扫描，每次扫描称为一趟。当发现相邻相邻两个数据的次序与排序要求的大小次序不符合次序不符合时，即将这两个数据进进行互换行互换。这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。第三张，PPT共十七页，创作于2022年6月例：用冒泡排序的方法将下面一组无序数组例：用冒泡排序的方法将下面一组无序数组排成从小到大排成从小到大 49,38,65,97,76,13,27,49 49,38,65,97,76,13,27,49 分析：首先为了方便分析，我们把所给的数据分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：先用一个表格列出来，如下：第四张，PPT共十七页，创作于2022年6月对比原数据经过第一趟排序，实现了什么目的？对比原数据经过第一趟排序，实现了什么目的？第一趟排序，一共进行了多少次比较？第一趟排序，一共进行了多少次比较？49492727131376769797656538384949数据数据8 87 76 65 54 43 32 21 1序号序号4938,交换位置原数据和序号原数据和序号序号序号1 12 23 34 45 56 67 78 8数据数据49493838656597977676131327274949第一趟排序第一趟排序的步骤：的步骤：序号序号1 12 23 34 45 56 67 78 8数据数据38384949656597977676131327274949序号序号1 12 23 34 45 56 67 78 8数据数据38384949656597977676131327274949序号序号1 12 23 34 45 56 67 78 8数据数据38384949656597977676131327274949序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576769797131327274949序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313979727274949序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313272797974949序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313272749499797经过第一趟排序，把最大的数沉到最底了！经过第一趟排序，把最大的数沉到最底了！4965,保持不变6576,交换位置9713,交换位置9727,交换位置9749,交换位置第五张，PPT共十七页，创作于2022年6月经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了经过第二趟排序，把第二大的数沉到倒数第二个位置了!97974949272713137676656549493838数据数据8 87 76 65 54 43 32 21 1序号序号3849,保持不变第一趟排序后的数据和序号第一趟排序后的数据和序号第二趟排序第二趟排序的步骤：的步骤：序号序号1 12 23 34 45 56 67 78 8数据数据383849496565767613132727494997974965,保持不变6513,交换位置7627,交换位置7649,交换位置序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313272749499797序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313272749499797序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313272749499797序号序号1 12 23 34 45 56 67 78 8数据数据38384949656513137676272749499797序号序号1 12 23 34 45 56 67 78 8数据数据38384949656513132727767649499797序号序号1 12 23 34 45 56 67 78 8数据数据3838494965651313272749497676979776R2是是否否如何交换数据，这样行吗？R2R3是是否否t:=R2R2:=R3R3:=t不断的这样画下去要画多少个类似的选择结构？有没有办法让流程图更加简洁呢？这样交换数据，会有什么问题？分析：第九张，PPT共十七页，创作于2022年6月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.画出第一趟排序的算法流程图：用简洁的循环结构进行表示用简洁的循环结构进行表示第十张，PPT共十七页，创作于2022年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分析：后面的排序只要按照这种方法不断进行就行了。2、按照这种画法第二趟、第三趟、第四趟排序的流程图、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？第十一张，PPT共十七页，创作于2022年6月是是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分析：这是一个两重循环结构第十二张，PPT共十七页，创作于2022年6月思考交流：w在我们刚才的算法流程图中，每一趟的排序我们都进行了7次，是否每一趟的排序都需要进行7次比较呢？w那么现在请你对我们刚才画出的算法流程图进行优化，设计出更好的流程图避免不必要的工作。第十三张，PPT共十七页，创作于2022年6月观察原数据与第一、二趟排序后的数据观察原数据与第一、二趟排序后的数据序号序号1 12 23 34 45 56 67 78 8数据数据38384949656576761313272749499797序号序号1 12 23 34 45 56 67 78 8数据数据38384949656513132727494976769797序号序号1 12 23 34 45 56 67 78 8数据数据49493838656597977676131327274949我们知道经过第一趟的排序之后，最大的一个数我们知道经过第一趟的排序之后，最大的一个数已经排到最后了这样在进行第二趟排序时有没有已经排到最后了这样在进行第二趟排序时有没有必要再对第必要再对第7 7、8 8个数据再进行排序呢？个数据再进行排序呢？第十四张，PPT共十七页，创作于2022年6月参照我们第一趟排序的画法、第二趟排序的流程图参照我们第一趟排序的画法、第二趟排序的流程图此时只需进行此时只需进行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分析：第十五张，PPT共十七页，创作于2022年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分析：第十六张，PPT共十七页，创作于2022年6月感感谢谢大大家家观观看看2022/10/19第十七张，PPT共十七页，创作于2022年6月
