3.4.1冒泡法排序算法.ppt

1、算法与程序设计,益阳市箴言中学 周国华,冒泡法排序,排序:把杂乱无章的数据变为有序的数据的过程。 （递增或递减）,冒泡排序:一种最简单，最直观，最广泛使用的排序法。,冒泡排序法又是如何实现对数据进行有序排序的呢？,任务一： 观看冒泡排序舞蹈 分组讨论并总结冒泡排序的方法 （10分）,初识冒泡,任务一： 观看冒泡排序舞蹈 分组讨论并总结冒泡排序的方法 （10分）,初识冒泡,初探冒泡,排序的基本原理 、按从前往后的方向进行多趟比较。 、当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。,任务二：(两人一组） 、用冒泡法排序，将5张牌从左到右按由小到大的顺序排列 、在表一

2、中，记录比较的趟数与每趟比较次数，并进行初步的分析。,任务二：(两人一组） 、用冒泡法排序，将5张牌从左到右按由小到大的顺序排列 、在表一中，记录比较的趟数与每趟比较次数，并进行初步的分析。,深探冒泡-实例探究,讲解与演示（10分） 纠错得分（1处+5分）,冒泡排序知识抢答,答对加10分，答错减5分,知识抢答,答对加10分，答错减5分,、如果有8个数进行冒泡 排序，则要进行趟比较,7,知识抢答,答对加10分，答错减5分,2、如果有个数进行冒泡 排序，则要进行趟比较,-1,知识抢答,答对加10分，答错减5分,3、5个数第2趟冒泡要经过次比较,3,知识抢答,答对加10分，答错减5分,4、个数第1趟

3、冒泡要经过次比较,-1,知识抢答,答对加10分，答错减5分,5、个数第j趟冒泡要经过次比较,-j,知识抢答,答对加10分，答错减5分,6、个数第j趟冒泡，确定了第几大值。（从左至右，由小到大冒泡排序）,j,知识抢答,答对加10分，答错减5分,7、个数，趟数与本趟中比较次数间关系,趟数+比较次数个数(N),对“648251”中的6个数码，从左到右按小到大要求进行二趟冒泡排序后即为某游戏中数字密码锁的密码，该密码是（ ）,牛刀小试,第一趟后：462518,第二趟后：425168,648251,冒泡排序规律总结,冒泡排序规律总结,个数进行冒泡排序，则要进行 N -1趟比较,个数j趟冒泡排序要经过N-

4、j 次比较,个数，趟数与本趟中比较次数间关系 个数第j趟冒泡，确定了第j大值。 （从左至右，由小到大冒泡排序）,趟数+比较次数个数(N),冒泡排序规律总结,个数进行冒泡排序，则要进行 N -1趟比较,个数j趟冒泡排序要经过N-j 次比较,个数，趟数与本趟中比较次数间关系 个数第j趟冒泡，确定了第j大值。 （从左至右，由小到大冒泡排序）,趟数+比较次数个数(N),若能在画流程图与编写程序中熟练运用， 可精简代码，提高程序的运行效率！,冒泡排序原理,排序的基本原理 、按从前往后的方向进行多趟比较。 、当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。,为什么叫冒泡法排序

5、呢？,冒泡排序原理,所谓冒泡排序，形象的说，就是在将一组数据从小到大的顺序排列时，小的数据视为质量较轻，大的数据视为质量较重，小的数据好比水中的气泡，往上方（前）移动，较大的数据好比是石头，往下方（后）沉，最重的会沉到底，最轻的会浮到顶，反复进行比较，直到数据列排成有序列。这样，整个过程，好象气泡向上浮起一样。,排序的基本原理 、按从前往后的方向进行多趟比较。 、当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。,为什么叫冒泡法排序呢？,冒泡排序原理,所谓冒泡排序，形象的说，就是在将一组数据从小到大的顺序排列时，小的数据视为质量较轻，大的数据视为质量较重，小的数据好

6、比水中的气泡，往上方（前）移动，较大的数据好比是石头，往下方（后）沉，最重的会沉到底，最轻的会浮到顶，反复进行比较，直到数据列排成有序列。这样，整个过程，好象气泡向上浮起一样。,排序的基本原理 、按从前往后的方向进行多趟比较。 、当发现相邻两个数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。,为什么叫冒泡法排序呢？,读画流程图,任务三： 画冒泡法排序算法流程图,读画流程图,下面我们继续考虑，将我们刚才排序的全过程用算法流程图表示出来。,我们把它分成几步来做，第一步，先把第一趟的排序用流程图描述出来。,假设有数据列为 R(1), R(2), R(3), R(4), R(5),R(

7、1 ) :=R(2 ),t:=R(1) R(1):=R(2) R(2):= t,开始,第一步做什么？,如何交换数据，这样行吗？,t:=R(2) R(2):=R(3) R(3):= t,不断的这样画下去要画多少个类似的选择结构？,有没有办法让流程图更加简洁呢？,这样交换数据，会有什么问题？,1.画出第一趟排序的算法流程图：,分析：,否,是,i:= i +1,开始,i:=1,R(i ) R(i +1 ),t:=R(i ) R(i ) :=R(i +1 ) R(i +1 ) := t,分析：,用简洁的循环结构进行表示,分析：后面的排序只要 按照这种方法不断进行就 行了。,2、后面排序的算法流程图怎么

8、画？,那么同样的结构要进行多少次呢？,有没有办法让流程图更加简洁呢？,是,3、怎样把整个冒泡排序的流程图画出来？,开始,j:=1,否,j:=j1,这是一个两重循环结构,i 5-j,牛刀小试,画出用冒泡排序对个数字，从左到右按升序进行排序的流程图,是,开始,j:=1,否,j:=j1,i N-j,j-1,小结：,本节课主要学习了冒泡排序的基本原理及其算法流程图。其中数组和双循环是我们本节课使用较多的一种结构。,个数进行冒泡排序，则要进行 N -1趟比较,个数j趟冒泡排序要经过N-j 次比较,个数，趟数与本趟中比较次数间关系 个数第j趟冒泡，确定了第j大值。 （从左至右，由小到大冒泡排序）,趟数+比较次数个数(N),扩展:,冒泡排序也可以从后往前进行,扩展:,冒泡排序也可以从后往前进行,扩展:,冒泡排序也可以从后往前进行,扩展:,冒泡排序也可以从后往前进行,扩展:,课后作业： 设计从后往前进行降序的冒泡法排序算法，并画出相应的流程图。,课堂学习评价,1、评价课堂学习（自评、组评