资源简介

(共22张PPT)
复习 循环嵌套
——冒泡排序
学习目标：
1.能正确理解冒泡思想
2.能运用冒泡解决排序问题
排序算法
排序的含义及方式
(1)所谓排序就是将无序的数据变成有序的数据。
(2)排列方式有升序(也称递增,即从小到大排列)和降序。
排序要求： 每一次只能取两个数进行比较。
冒泡排序
情景：
观察水中的气泡往上冒的情景，有什么特点呢？
冒泡原理
冒泡排序和气泡在水中不断往上冒的情况有些
类似。气泡大的（大的数据）在下面，气泡小
的（小的数据）在上面。
冒泡排序的基本原理
冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素，若为逆序（递增或递减）则进行交换。将待排序元素从上至下比较一遍称为一趟“冒泡”或是一遍排序。每趟冒泡都将待排序列中的最小关键字交换到最上（或最下）位置，直到全部元素有序为止。
这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。
例：用冒泡排序的方法将下面一组无序数组
排成从小到大的顺序。
t=[ 49,38,76,97,65 ]
分析：首先为了方便分析，我们把所给的数据
先用一个表格列出来，如下：
实例
算法分析
序号 数据
t[0] 49
t[1] 38
t[2] 76
t[3] 97
t[4] 65
序号 数据
t[0] 38
t[1] 49
t[2] 76
t[3] 97
t[4] 65
序号 数据
t[0] 38
t[1] 49
t[2] 76
t[3] 97
t[4] 65
序号 数据
t[0] 38
t[1] 49
t[2] 76
t[3] 97
t[4] 65
序号 数据
t[0] 38
t[1] 49
t[2] 76
t[3] 65
t[4] 97
序号 数据
t[0] 38
t[1] 49
t[2] 76
t[3] 65
t[4] 97
第一趟排序，一共进行了多少次比较？
4次
对比原数据经过第一趟排序，实现了什么目的？
经过第一趟排序，把最大的数沉到最底了！
序号 数据
t[0] 38
t[1] 49
t[2] 76
t[3] 65
t[4] 97
序号 数据
t[0] 38
t[1] 49
t[2] 65
t[3] 76
t[4] 97
序号 数据
t[0] 38
t[1] 49
t[2] 65
t[3] 76
t[4] 97
第一趟
第二趟
第三趟
第四趟
序号 数据
t[0] 38
t[1] 49
t[2] 65
t[3] 76
t[4] 97
序号 数据
t[0] 38
t[1] 49
t[2] 65
t[3] 76
t[4] 97
经过第二趟排序，实现了什么目的？
经过第二趟排序，把第二大的数沉到倒数第二个位置了!
问：后面我们要几趟这样的对比
5个数字，需要 趟比较，每趟进行 次比较
6个数字呢？
4
4
N个数字呢？
5，5
n-1，n-1
序号 数据
t[0] 49
t[1] 38
t[2] 76
t[3] 97
t[4] 65
原始
例题：
下面我们继续考虑，将我们刚才排序的全过程用算法流程图表示出来。
我们把它分成几步来做，第一步，先把第一趟的排序用流程图描述出来。
假设该数据列为
t[0]，t[1], t[2], t[3], t[4],
序号 数据
t[0] 49
t[1] 38
t[2] 76
t[3] 97
t[4] 65
1.画出第一趟排序的算法流程图：
第一次：t[0]>t[1]
第二次：t[1]>t[2]
第三次：t[2]>t[3]
第四次：t[3]>t[4]
t[0]=t[1]
a=t[0]
t[0]=t[1]
t[1]= a
开始
第一步做什么？
t[0]>t[1]
是
否
如何交换数据，这样行吗？
t[1]>t[2]
是
否
a=t[1]
t[1]=t[2]
t[2]= a
…
不断的这样画下去要画多少个类似的选择结构？
这样交换数据，会有什么问题？
1.画出第一趟排序的算法流程图：
分析：
序号 数据
t[0] 49
t[1] 38
t[2] 76
t[3] 97
t[4] 65
有没有办法让流程图更加简洁呢？
t[0]>t[1]
R[1]=R[2]
是
否
a=t[0]
t[0]=t[1]
t[1]= a
是
否
i= i +1
结束
开始
t[0]>t[1]
R[1]=R[2]
是
否
a=t[0]
t[0]=t[1]
t[0]= a
i=0
t[i ]>t[i +1]
i <4
a=t[i ]
t[i ]=t[i +1]
t[i +1]=a
分析：
用简洁的循环结构进行表示
t[0]>t[1]
t[1]>t[2]
t[2]>t[3]
t[3]>t[4]
=t[i]>t[i+1]
i=0:
i=1:
i=2:
i=3:
=t[i]>t[i+1]
=t[i]>t[i+1]
=t[i]>t[i+1]
循环变量：
循环条件：
i<4
i=0
是
否
i= i +1
结束
开始
R[1]>R[2]
R[1]=R[2]
是
否
t=R[2]
R[1]=R[2]
R[2]= t
i=0
t[i ]>t[i +1]
a=t[i ]
t[i ]=t[i +1]
t[i +1]=a
i <4
分析：后面的排序只要
按照这种方法不断进行就
行了。
2、后面排序的算法流程图怎么画？
那么同样的结构要进行多少次呢？
有没有办法让流程图更加简洁呢？
否
3、怎样把整个冒泡排序的流程图画出来？
开始
结束
j<4
j=0
是
j=j＋1
否
i <4
是
i=0
i= i +1
是
否
t[i ]>t[i +1]
a=t[i ]
t[i ]=t[i +1]
t[i +1]= a
这是一个两重循环结构
否
4、怎样把整个冒泡排序的程序写出来？
开始
结束
j<4
j=0
是
j=j＋1
否
i <4
是
i=0
i= i +1
是
否
t[i ]>t[i +1]
a=t[i ]
t[i ]=t[i +1]
t[i +1]= a
小结：
本节课主要学习了冒泡排序的基本原理及其算法流程图。其中列表和双循环是我们本节课使用较多的一种结构。
应用到本节知识的实例有很多，比如：打印九九乘法口诀表、彩票数字选择器、工作表安排等等。
拓展：
在刚才的冒泡排序中是否一定要进行4趟？第一趟都进行4次的对比，针对这个问题你有什么好的方法对我们的算法再进行优化？
内层循环对比递减设计
j=0
j=1
j=2
j=3
4
3
2
1
4
4
4
4
次数
次数
外层
否
开始
结束
j<4
j=0
是
j=j＋1
否
i <4
是
i=0
i= i +1
是
否
t[i ]>t[i +1]
a=t[i ]
t[i ]=t[i +1]
t[i +1]= a
扩展:
12
35
32
29
64
78
34
45
冒泡排序也可以从后往前进行，过程演示如下：
否
开始
结束
j<4
j=0
是
j=j＋1
否
i <4-j
是
i=0
i= i +1
是
否
t[i ]>t[i +1]
a=t[i ]
t[i ]=t[i +1]
t[i +1]= a
第一次：t[0]>t[1]
第二次：t[1]>t[2]
第三次：t[2]>t[3]
第四次：t[3]>t[4]
谢谢！

展开更多......

收起↑