2022年数据结构-冒泡排序教案.docx

《2022年数据结构-冒泡排序教案.docx》由会员分享，可在线阅读，更多相关《2022年数据结构-冒泡排序教案.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学习必备 欢迎下载冒泡排序教案教学目的1. 学问与技能：1）明白排序及冒泡排序的概念及特点；2）把握冒泡法排序的原理；3）把握冒泡法排序的优化；4）初步把握冒泡排序的程序实现；2过程与方法：懂得冒泡排序的分析过程,并初步把握用冒泡排序算法来设计解决简洁的排序问题；3. 课时安排： 1 课时教学重点冒泡排序算法的原理；教学难点分析冒泡排序的实现过程；教学方法讲授法、示例法与练习法结合；教学用具板书教学过程一、复习回忆什么是排序： 排序是把一个无序的数据元素序列整理成有规律的按排序关键字递增（或递减）排列的有序序列的过程；排序过程的两种基本操作：1

2、 比较两个关键字的大小2 将记录从一个位置移动到另一个位置；名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载二、冒泡排序1、冒泡排序（ bubble sort）的概念冒泡排序（ Bubble Sort）是一种简洁的排序算法；它重复地走访要排序的数列,一次比较两个元素, 假如他们的次序错误就把他们交换过来；需要交换的数据, 也就是说该序列已经排序完成；经由交换渐渐“ 浮” 到序列的顶端；2、冒泡排序的思想走访序列的工作是重复地进行直到没有 这个算法的名字由来是由于越小的元素会将待排序序列中第一个记录的关键字R1.k

3、ey 与其次个记录的关键字R2.key 作比较,如果 R1.keyR2.key ,就交换记录R1 和 R2 在序列中的位置,否就不交换；然后连续对当前序列中的其次个记录和第三个记录作同样的处理,依此类推, 直到序列中第 n-1 个和第 n 个记录处理完为止, 我们称这样的过程为第一趟起泡排序,其结果使得关键字最大的记录被安置到最终一个记录的位置上；然后进行其次趟起泡排序对前 n-1 个记录进行同样的操作,其结果是使关键字次大的记录被安置到第 序,直到排序完成；n-1 个记录的位置上； 然后进行第三、 四 趟起泡排同时用流程图的方式板书其思想,流程图如下图所示：开头N N N 个数据的序列an

4、I=i+1 定义变量并赋值i,j,temp in-1 j=j+1 Y N jaj+1 Y 利用 temp 交换 aj 、aj+1 的值终止名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载3、课堂示例第一题： 97 66 49 38 26 17 9 6 第一趟排序结果：66 49 38 26 17 9 6 97 其次趟排序结果：49 38 26 17 9 6 66 97 第三趟排序结果：38 26 17 9 6 49 66 97 第四趟排序结果：26 17 9 6 38 49 66 97 第五趟排序结果：17 9

5、6 26 38 49 66 97 第六趟排序结果：9 6 17 26 38 49 66 97 第七趟排序结果：6 9 17 26 38 49 66 97 最终结果序列： 6 9 17 26 38 49 66 97 其次题： 6 9 17 26 38 49 66 97 第一趟排序结果：6 9 17 26 38 49 66 97 其次趟排序结果：6 9 17 26 38 49 66 97 第三趟排序结果：6 9 17 26 38 49 66 97 第四趟排序结果：6 9 17 26 38 49 66 97 第五趟排序结果：6 9 17 26 38 49 66 97 第六趟排序结果：6 9 17 2

6、6 38 49 66 97 第七趟排序结果：6 9 17 26 38 49 66 97 最终结果序列： 6 9 17 26 38 49 66 97 4、由练习引出1 、一次冒泡排序的结果：使关键字最大的记录排在了序列的最终一个位置上；（很重要）2 、冒泡排序的特点：第一,. “编程复杂度 ”很低,很简洁写出代码；其次,具有稳固性,这里的稳固性是指原序列中相同元素的相对次序仍旧保持到排序后的序列,3 、比较两题的题目区分和排序过程区分；第一题是一组逆序数据,每一趟排序都进行了数据交换,共进行了 8-1=7 次冒泡； 其次题是一组正序数据,进行完一次排序后就发觉,没有任何数据交换发生,后面进行的其

7、次次到第七次冒泡的过程完全一样；三、冒泡排序的优化课堂摸索题：考虑任何一组序列最多进行多少次冒泡排序就可保证次序已经排好了；摸索： 假如序列初始次序是逆序,需要进行多少次排序？假如序列初始次序是正序,需要进行多少次排序就可以保证数据序列次序？如何使排序过程适可而止,既排好序又不余外进行？当运算机对一组数据进行排序之前,并不知道该组数据是什么次序,因此, 必需要进行至少一次的比较和排序,当某一比较和排序进行完之后发觉没有任何数据交换发生,证明任何相邻的两数都符合目标次序要求,因此,也不必再进行下一次比较排序了；结论： 当进行某次冒泡排序时,如没有任何两个记录交换位置,就说明序列已排好,此时排序可

8、终止；名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - 学习必备 欢迎下载四、用文字描述冒泡排序算法摸索方法：第一是对数组的相邻的两数比较,依据比较结果确定是否交换位置；这种比较进行的次 数比数据列中数据个数少 1；（此两步完成了一次冒泡排序）对一个序列来说, 共进行多少次冒泡排序呢？最多和上面其次步的比较次数一样,但也 可提前终止, 只要在某一遍冒泡中没有发生数据交换即可；如何确定是否发生数据交换,在 程序中,可以考虑设置一个标志位,当发生数据交换时,更换标志位, 每次重新进行冒泡排 序之前可以检查标志位,假如没有发生转变,就可证

9、明上一次冒泡已经没有数据交换发生,也就是说数据序列已经排好,可以停止进行冒泡排序；冒泡算法函数 设置标志位； / 以下循环用来掌握冒泡排序进行的次数 for 循环（对 n 个数据的序列进行 n-1 次冒泡,但是假如没有交换发生就跳出该循环） 设置标志位值；/ 以下循环用来对该数据序列进行一次冒泡排序 for（单次冒泡排序需要进行n-i-1次） 比较相邻两数的大小；if 前大后小 交换 转变标志位 else / 前小后大 位置不变 总结本节课：1.第一回忆了什么是排序；因此我们总2.然后介绍了冒泡排序的思想；（每次冒一个泡泡,把最大的冒到最终）3.通过三道练习题对一组无序数据进行了排序；4.通过

10、练习题我们看出来,数据初始序列越接近目标序列,冒泡的次数越少；结出了冒泡排序最多进行的次数和终止的条件；名师归纳总结 5.最终,我们依据冒泡排序的思想用文字描述了冒泡函数的构成方法；第 4 页,共 5 页- - - - - - -精选学习资料 - - - - - - - - - 学习必备 欢迎下载作业1、用冒泡排序法对数字序列进行排序（要写出 6 次排序步骤）60 55 48 37 10 97 74 答 55 48 37 10 60 74 97 48 37 10 55 60 74 97 37 10 48 55 60 74 97 10 37 48 55 60 74 97 10 37 48 55 60 74 97 10 37 48 55 60 74 97 2、用 C语言描述冒泡排序算法；Void BubbleSortint x,int n / 传入序列和序列数字个数 Int i =0; j =0; int int flag =1; int temp; fori=0;in-1 & flag=1;i+ flag=0; forj=0;j xj+1 flag=1; temp=xj; xj=xj+1; xj+1=temp; 名师归纳总结 - - - - - - -第 5 页,共 5 页