1、学习目标：学习目标：1.能正确理解冒泡思想能正确理解冒泡思想2.能运用冒泡解决排序问题能运用冒泡解决排序问题排序算法 排序要求：排序要求：每一次只能取两个数进行比较。每一次只能取两个数进行比较。冒泡排序冒泡排序情景：情景：观察水中的气泡往观察水中的气泡往上冒的情景，有什上冒的情景，有什么特点呢？么特点呢？冒泡原理冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡类似。气泡大的大的（大的数据）在（大的数据）在下面下面，气泡，气泡小小的的（小的数据）在（小的数据）在上面上面。冒泡排序的基本原理冒泡排序的基本原理 冒泡排序（冒泡排序（Bubble so
2、rtBubble sort）是基于交换排序的一种算）是基于交换排序的一种算法。它是依次法。它是依次两两比较待排序元素两两比较待排序元素，若为逆序（递增或，若为逆序（递增或递减）则进行交换。将待排序元素从上至下比较一遍称递减）则进行交换。将待排序元素从上至下比较一遍称为一趟为一趟“冒泡冒泡”或是一遍排序。每趟冒泡都将待排序列或是一遍排序。每趟冒泡都将待排序列中的中的最小关键字交换到最上（或最下）位置最小关键字交换到最上（或最下）位置，直到全部，直到全部元素有序为止。元素有序为止。这样，较小的数据就会逐个向前移动，好象气泡向上浮这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。起一样。例：用
3、冒泡排序的方法将下面一组无序数组例：用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。排成从小到大的顺序。t=49,38,76,97,65 t=49,38,76,97,65 分析：首先为了方便分析，我们把所给的数据分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：先用一个表格列出来，如下：实例实例算法分析算法分析序序号号数数据据t049t138t276t397t465序序号号数数据据t038t149t276t397t465序序号号数数据据t038t149t276t397t465序序号号数数据据t038t149t276t397t465序序号号数数据据t038t149t276t
4、365t497序序号号数数据据t038t149t276t365t497序序号号数数据据t038t149t276t365t497序序号号数数据据t038t149t265t376t497序序号号数数据据t038t149t265t376t497第一趟第一趟第二趟第二趟第三趟第三趟第四趟第四趟序序号号数数据据t038t149t265t376t497序序号号数数据据t038t149t265t376t497问：后面我们要几趟这样的对比问：后面我们要几趟这样的对比5个数字，需要个数字，需要 趟比较，每趟进行趟比较，每趟进行 次比较次比较6个数字呢？个数字呢？44N个数字呢？个数字呢？5，5n-1，n-1序序
5、号号数数据据t049t138t276t397t465原始原始例题：例题：下面我们继续考虑，将我们刚才排序的下面我们继续考虑，将我们刚才排序的全过程用算法流程图表示出来。全过程用算法流程图表示出来。我们把它分成几步来做，第一步，先把我们把它分成几步来做，第一步，先把第一趟的排序用流程图描述出来。第一趟的排序用流程图描述出来。假设该数据列为假设该数据列为t0，t1,t2,t3,t4,序序号号数数据据t049t138t276t397t4651.1.画出第一趟排序的算法流程图：画出第一趟排序的算法流程图：第一次：第一次：t0t1第二次：第二次：t1t2第三次：第三次：t2t3第四次：第四次：t3t4t
6、0=t1a=t0t0=t1t1=a开始开始第一步做什么？t0t1是是否否如何交换数据，这样行吗？t1t2是是否否a=t1t1=t2t2=a不断的这样画下去要画多少个类似的选择结构？这样交换数据，会有什么问题？1.1.画出第一趟排序的算法流程图：画出第一趟排序的算法流程图：分析：分析：序序号号数数据据t049t138t276t397t465有没有办法让流程图更加简洁呢？t0t1R1=R2是是否否a=t0t0=t1t1=a是是否否i=i+i=i+1 1结束结束开始开始t0t1R1=R2是是否否a=t0t0=t1t0=ai=i=0 0ti i ti i+1i 4i t1t1t2t2t3t3t4=ti
7、ti+1i=0:i=1:i=2:i=3:=titi+1=titi+1=titi+1循环变量：循环变量：循环条件：循环条件：iR2R1=R2是是否否t=R2R1=R2R2=ti=i=0 0ti i ti i+1a=ti i ti i=ti i+1ti i+1=ai 4i 4分析：后面的排序只要分析：后面的排序只要按照这种方法不断进行就按照这种方法不断进行就行了。行了。2 2、后面排序的算法流程图怎么画？、后面排序的算法流程图怎么画？那么同样的结构要进行多少次呢？有没有办法让流程图更加简洁呢？否否3、怎样把整个冒泡排、怎样把整个冒泡排序的流程图画出来？序的流程图画出来？开始开始结束结束j4j4j=
8、j=0 0 是是j=j=j j1 1否否i i ti i+1a=ti i ti i=ti i+1ti i+1=a这是一个两重循环结构这是一个两重循环结构否否4、怎样把整个冒泡排怎样把整个冒泡排序的程序写出来？序的程序写出来？开始开始结束结束j4j4j=j=0 0 是是j=j=j j1 1否否i i ti i+1a=ti i ti i=ti i+1ti i+1=a 小结：小结：本节课主要学习了冒泡排序的本节课主要学习了冒泡排序的基本原理基本原理及其及其算法流程图算法流程图。其中。其中列表列表和和双循环双循环是我们是我们本节课使用较多的一种结构。本节课使用较多的一种结构。应用到本节知识的实例有很多
9、，比如：应用到本节知识的实例有很多，比如：打印九九乘法口诀表、彩票数字选择器、工打印九九乘法口诀表、彩票数字选择器、工作表安排等等。作表安排等等。拓展：拓展：在刚才的冒泡排序中是否一定要进行在刚才的冒泡排序中是否一定要进行4 4趟？第一趟都进行趟？第一趟都进行4 4次次的对比，针对这个问题你有什么好的方法对我们的算法再进行的对比，针对这个问题你有什么好的方法对我们的算法再进行优化？优化？内层循环对比递减设计内层循环对比递减设计j=0j=1j=2j=343214444次数次数次数次数外层外层否否开始开始结束结束j4j4j=j=0 0 是是j=j=j j1 1否否i i ti i+1a=ti i ti i=ti i+1ti i+1=a 扩展扩展:1235322964783445 冒泡排序也可以从后往前进行，过程演示冒泡排序也可以从后往前进行，过程演示如下：如下：否否开始开始结束结束j4j4j=j=0 0 是是j=j=j j1 1否否i i ti i+1a=ti i ti i=ti i+1ti i+1=a第一次：第一次：t0t1第二次：第二次：t1t2第三次：第三次：t2t3第四次：第四次：t3t4
