冒泡排序(公开课课件)

冒泡排序海门中专11E02班复习：请简单叙述顺序比较排序法和选择排序法的排序过程（以升序为例）物理教师年终工作总结2016年已经过去，对我来说是紧张忙碌而又收获多多，对于刚进三中的我各方面的压力比较大，于是我积极调整心态，适用学校的一切，本学期我担高一(7)班和高一(11)的物理教学工作，半年来，本人以学校及各处组工作计划为指导;以加强师德师风建设，提高师德水平为重点，以提高教育教学成绩为中心，以深化课改实验工作为动力，认真履行岗位职责，较好地完成了工作目标任务，从而提高自己的教学水平和思想觉悟，回顾这半年，忙碌而又充实，付出了，努力了，收获了，也成熟了。现将本学期的工作做一个小结，总结过去，展望未来，寄望明天工作的更好。一、教学工作在教学工作中，我认真备课、上课、经常听老教师的课、和他们一起评课，做好课后辅导工作，努力形成比较完整的知识结构，多挖掘教材，多思索教法，多研究学生。平时上课严格要求学生，尊重学生，发扬教学民主，使学生学有所得，不断提高自己的教学水平和思想觉悟，顺利的完成了教育教学任务。备课深入细致，力求深入理解教材，准确把握难重点。在制定教学目标时，非常注意学生的实际情况。请教老教师，教案编写认真，并不断归纳总结经验教训。在教学中注意抓住重点情景：1.观察水中的气泡往上冒的情景，气泡往上冒的时候有什么特点呢？冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的（大的数据）在下面，气泡小的（小的数据）在上面。冒泡排序的基本原理是对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。排序时每次对相邻两个元素进行比较，如果它们的排序与要求的大小次序不符合时，即将这两个数据进行互换。这样，各元素就会像水中冒气泡一样通过交换调到它们的正确位置。例：用冒泡排序的方法将下面一组无序的数排成从小到大的顺序{49,38,65,97,76,13,27,49}分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：对比原数据经过第一趟排序，实现了什么目的？第一趟排序，一共进行了多少次比较？4927137697653849数据76543210序号4938,交换位置原数据和序号序号01234567数据4938659776132749第一趟排序的步骤：序号01234567数据3849659776132749序号01234567数据3849659776132749序号01234567数据3849659776132749序号01234567数据3849657697132749序号01234567数据3849657613972749序号01234567数据3849657613279749序号01234567数据3849657613274997经过第一趟排序，把最大的数沉到最底了！4965,保持不变6597,保持不变9776,交换位置9713,交换位置9727,交换位置9749,交换位置经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了!9749271376654938数据76543210序号3849,保持不变第一趟排序后的数据和序号第二趟排序的步骤：序号01234567数据38496576132749974965,保持不变6576,保持不变7613,交换位置7627,交换位置7649,交换位置序号01234567数据3849657613274997序号01234567数据3849657613274997序号01234567数据3849657613274997序号01234567数据3849651376274997序号01234567数据3849651327764997序号01234567数据38496513274976977697,保持不变序号01234567数据3849651327497697观察原数据与第一、二趟排序后的数据序号01234567数据3849657613274997序号01234567数据3849651327497697序号01234567数据4938659776132749问：为了使这一组无序数组完全按照要求排成从小到大我们还需不需要再继续排序呢？问：那么我们预计最多一共要经过多少次排序呢？例题：下面我们继续考虑，将我们刚才排序的全过程用算法流程图表示出来。我们把它分成几步来做，第一步，先把第一趟的排序用流程图描述出来。t=R[0]R[0]=R[1]R[1]=t开始1.画出第一趟排序的算法流程图：假设该数据列为R[0],R[1],R[2],R[3],R[4],R[5],R[6],R[7]第一步做什么？R[0]R[1]是否R[1]R[2]是否t=R[1]R[1]=R[2]R[2]=t…不断的这样画下去要画多少个类似的选择结构？有没有办法让流程图更加简洁呢？分析：R[0]R[1]R[1]=R[2]是否t=R[0]R[0]=R[1]R[1]=t是否j=j+1结束开始R[0]R[1]R[1]=R[2]是否t=R[0]R[0]=R[1]R[1]=tj=0R[j]R[j+1]j=6t=R[j]R[j]=R[j+1]R[j+1]=t分析：1.画出第一趟排序的算法流程图：用简洁的循环结构进行表示是否j=j+1结束开始R[1]R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=tj=0R[j]R[j+1]t=R[j]R[j]=R[j+1]R[j+1]=tj=6分析：后面的排序只要按照这种方法不断进行就行了。2、按照这种画法第二趟、第三趟、第四趟排序的流程图怎样画？怎样把整个冒泡排序的流程图画出来？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？否3、怎样把整个冒泡排序的流程图画出来？开始结束i=7i=1是i=i＋1否j=6是j=0j=j+1是否R[j]R[j+1]t=R[j]R[j]=R[j+1]R[j+1]=t分析：这是一个两重循环结构思考交流：在我们刚才的算法流程图中，每一趟的排序我们都进行了7次，是否每一趟的排序都需要进行7次比较呢？那么现在请你对我们刚才画出的算法流程图进行优化，设计出更好的流程图避免不必要的工作。参照我们第一趟排序的画法、第二趟排序的流程图此时只需进行6次。是否j=j+1结束开始R[1]R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=tj=0R[j]R[j+1]t=R[j]R[j]=R[j+1]R[j+1]=tj=6是否j=j+1结束开始R[1]R[2]R[1]=R[2]是否t=R[2]R[1]=R[2]R[2]=tj=0R[j]R[j+1]t=R[j]R[j]=R[j+1]R[j+1]=tj=5分析：否是j=7-i那么我们可以把整个冒泡排序的流程图优化成如图所示：开始结束否i=7i=1是i=i+1j=0j=j+1是否R[j]R[j+1]t=R[j]R[j]=R[j+1]R[j+1]=t分析：写出冒泡法程序段提问：冒泡法与前面所学的哪种排序方法相似？不同之处又在哪里？答：与顺序比较法相似，不同之处在于顺序比较法先确定a[0]，然后a[1]，a[2]，……，a[n-1]顺序确定。而冒泡法先确定a[n-1]，然后再按a[n-2]，……，a[0]顺序确定。用起泡法对十个数由大到小排序main(){inta[11],i,j,t;printf(“input10numbers:\n”);for(i=1;i11;i++)scanf(“%d”,&a[i]);printf(“\n”);for(j=1;j=9;j++)for(i=1;;i++)if(){a[i]=a[i+1];}printf(“\n”);for(i=1;i11;i++)printf(“%d”,a[i]);}i=10-ja[i]a[i+1]t=a[i];a[i+1]=t;课堂练习1.对6个元素的数组，用冒泡法进行排序时，共需比较趟，对n个元素的数组，则共需比较趟。3.编程题：数组中有7个元素，值为10，9，11，8，20，6，13，请用冒泡排序法，按由大到小排序后输出小结：(1)冒泡法排序程序段为（n个数据,升序）for(i=1;i=n-1;i++){for(j=0;j=n-1-i;j++)if(a[j+1]a[j]){t=a[j];a[j]=a[j+1];a[j+1]=t;}}（2）特点：算法思想为:相邻两数比较，根据排序要求，先确定最后一个数，然后依此类推，其算法思想较简单，一般适用于元素个数不多的场合。