冒泡排序算法

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

2、7页例：用冒泡排序的方法将下面一组无序数组排成从小到大 49,38,65,97,76,13,27,49 分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：现在学习的是第四页，共17页4938,交换位置原数据和序号第一趟排序的步骤：4965, 保持不变6576, 交换位置9713, 交换位置9727, 交换位置9749, 交换位置现在学习的是第五页，共17页3849,保持不变第一趟排序后的数据和序号第二趟排序的步骤：4965, 保持不变6513, 交换位置7627, 交换位置7649, 交换位置76R2是否如何交换数据，这样行吗？R2R3是否t:=R2R2:=R3R3:= t不断

3、的这样画下去要画多少个类似的选择结构？有没有办法让流程图更加简洁呢？这样交换数据，会有什么问题？分析：现在学习的是第九页，共17页R1R2R1=R2是否t=R1R1=R2R2= t否是i:= i +1结束开始R1R2R1=R2是否t=R1R1=R2R2= ti:=1Ri Ri +1i 7t:=Ri Ri :=Ri +1Ri +1:= t分析：1.画出第一趟排序的算法流程图： 用简洁的循环结构进行表示现在学习的是第十页，共17页否是i:= i +i:= i +1 1结束开始R1R2R1=R2是否t=R2R1=R2R2= ti:=i:=1 1Ri Ri +1t:=Ri i Ri i :=Ri i

4、+1Ri i +1:= ti 7分析：后面的排序只要按照这种方法不断进行就行了。2、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？现在学习的是第十一页，共17页是3、怎样把整个冒泡排序的流程图画出来？开始结束j7j:=j:=1 1否j:=j1是i 7否i:=i:=1 1i:= i +i:= i +1 1是否Ri Ri +1t:=Ri i Ri i :=Ri i +1Ri i +1:= t分析：这是一个两重循环结构现在学习的是第十二页，共17页思考交流：w在我们刚才的算法流程图中，每一趟的排序我

5、们都进行了7次，是否每一趟的排序都需要进行7次比较呢？w那么现在请你对我们刚才画出的算法流程图进行优化，设计出更好的流程图避免不必要的工作。现在学习的是第十三页，共17页观察原数据与第一、二趟排序后的数据我们知道经过第一趟的排序之后，最大的一个数已经排到最后了这样在进行第二趟排序时有没有必要再对第7、8个数据再进行排序呢？现在学习的是第十四页，共17页参照我们第一趟排序的画法、第二趟排序的流程图此时只需进行6次。否是i:= i +i:= i +1 1结束开始R1R2R1=R2是否t=R2R1=R2R2= ti:=i:=1 1Ri Ri +1t:=Ri i Ri i :=Ri i +1Ri i +1:= ti 7否是i:= i +i:= i +1 1结束开始R1R2R1=R2是否t=R2R1=R2R2= ti:=i:=1 1Ri Ri +1t:=Ri i Ri i :=Ri i +1Ri i +1:= ti 6分析：现在学习的是第十五页，共17页否是i j那么我们可以把整个冒泡排序的流程图优化成如图所示：开始结束否j0j:=j:=7 7是j:=j:=j-1j-1i:=i:=1 1i:= i +i:= i +1 1是否Ri Ri