浙教版（2019）高中信息技术选修1冒泡排序课件

1、 复习 循环嵌套 冒泡排序学习目标：1.能正确理解冒泡思想2.能运用冒泡解决排序问题排序算法排序的含义及方式(1)所谓排序就是将无序的数据变成有序的数据。(2)排列方式有升序(也称递增,即从小到大排列)和降序。排序要求： 每一次只能取两个数进行比较。冒泡排序情景：观察水中的气泡往上冒的情景，有什么特点呢？ 冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的（大的数据）在下面，气泡小的（小的数据）在上面。冒泡排序的基本原理 冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素，若为逆序（递增或递减）则进行交换。将待排序元素从上至下比较一遍称为一趟“冒

2、泡”或是一遍排序。每趟冒泡都将待排序列中的最小关键字交换到最上（或最下）位置，直到全部元素有序为止。 这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。例：用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。t= 49,38,76,97,65 分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下： 实例算法分析序号数据t049t138t276t397t465序号数据t038t149t276t397t465序号数据t038t149t276t397t465序号数据t038t149t276t397t465序号数据t038t149t276t365t497序号数据t038t149t2

3、76t365t497第一趟排序，一共进行了多少次比较？4次对比原数据经过第一趟排序，实现了什么目的？经过第一趟排序，把最大的数沉到最底了！序号数据t038t149t276t365t497序号数据t038t149t265t376t497序号数据t038t149t265t376t497第一趟第二趟第三趟第四趟序号数据t038t149t265t376t497序号数据t038t149t265t376t497经过第二趟排序，实现了什么目的？经过第二趟排序，把第二大的数沉到倒数第二个位置了!问：后面我们要几趟这样的对比5个数字，需要 趟比较，每趟进行 次比较6个数字呢？44N个数字呢？5，5n-1，n-1

4、序号数据t049t138t276t397t465原始例题： 下面我们继续考虑，将我们刚才排序的全过程用算法流程图表示出来。 我们把它分成几步来做，第一步，先把第一趟的排序用流程图描述出来。假设该数据列为t0，t1, t2, t3, t4, 序号数据t049t138t276t397t4651.画出第一趟排序的算法流程图：第一次：t0t1第二次：t1t2第三次：t2t3第四次：t3t4t0=t1a=t0t0=t1t1= a开始第一步做什么？t0t1是否如何交换数据，这样行吗？t1t2是否a=t1t1=t2t2= a不断的这样画下去要画多少个类似的选择结构？这样交换数据，会有什么问题？1.画出第一趟

5、排序的算法流程图：分析：序号数据t049t138t276t397t465有没有办法让流程图更加简洁呢？t0t1R1=R2是否a=t0t0=t1t1= a是否i= i +1结束开始t0t1R1=R2是否a=t0t0=t1t0= ai=0ti ti +1i t1t1t2t2t3t3t4 =titi+1i=0:i=1:i=2:i=3:=titi+1=titi+1=titi+1循环变量：循环条件： iR2R1=R2是否t=R2R1=R2R2= ti=0ti ti +1a=ti ti =ti +1ti +1=ai 4分析：后面的排序只要按照这种方法不断进行就行了。2、后面排序的算法流程图怎么画？那么同样

6、的结构要进行多少次呢？有没有办法让流程图更加简洁呢？否3、怎样把整个冒泡排序的流程图画出来？开始结束j4j=0 是j=j1否i ti +1a=ti ti =ti +1ti +1= a这是一个两重循环结构否4、怎样把整个冒泡排序的程序写出来？开始结束j4j=0 是j=j1否i ti +1a=ti ti =ti +1ti +1= a 小结： 本节课主要学习了冒泡排序的基本原理及其算法流程图。其中列表和双循环是我们本节课使用较多的一种结构。 应用到本节知识的实例有很多，比如：打印九九乘法口诀表、彩票数字选择器、工作表安排等等。 拓展： 在刚才的冒泡排序中是否一定要进行4趟？第一趟都进行4次的对比，针对这个问题你有什么好的方法对我们的算法再进行优化？内层循环对比递减设计j=0j=1j=2j=343214444次数次数外层否开始结束j4j=0 是j=j1否i ti +1a=ti ti =ti +1ti +1= a 扩展:1235322964783445冒