数据结构-冒泡排序教案

《数据结构-冒泡排序教案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、冒泡排序教案教学目的1.知识与技能：1）了解排序及冒泡排序的概念及特点；2）掌握冒泡法排序的原理；3）掌握冒泡法排序的优化；4）初步掌握冒泡排序的程序实现。2.过程与方法：理解冒泡排序的分析过程，并初步掌握用冒泡排序算法来设计解决简单的排序问题。3.课时分配：1课时教学重点冒泡排序算法的原理。教学难点分析冒泡排序的实现过程。教学方法讲授法、示例法与练习法结合。教学用具板书教学过程一、复习回顾什么是排序：排序是把一个无序的数裾元素序列整理成有规律的按排序关键字递增（或递减）排列的有序序列的过程。排序过程的两种基本操作：（1）比较两个关键字的大小（2）将记录从-个位置移动到另

2、一个位置。二、冒泡排序1、冒泡排序(bubblesort)的概念冒泡排序(BubbleSort)是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有耑要交换的数据，也就是说该序列已经排序完成。这个算法的名字由来是因为越小的元素会经巾交换慢慢“浮”到序列的顶端。2、冒泡排序的思想将待排序序列中第一个记录的关键字Rl.key与第二个记录的关键字R2.key作比较，如果Rl.key〉R2.key,则交换记录R1和R2在序列屮的位置，否则不交换；然后继续对当前序列中的第二个记录和第三个记录作同样的

3、处理，依此类推，直到序列中第n-1个和第n个记录处理完为止，我们称这样的过程为第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟起泡排序对前n-1个记录进行同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。然后进行第三、四……趟起泡排序，直到排序完成。同时用流程图的方式板书其思想，流程图如卜图所示：定义变fi并赋位i,j,temp利用temp交换a[j]、a[j+l]的值l=i+l结束3、课堂示例第一题：97664938261796第一趟排序结果：664938261796[97]第二趟排序结果：4938261796[

4、6697]第三趟排序结果：38261796[496697]第四趟排序结果：261796[38496697]第五趟排序结果：1796[2638496697]第六趟排序结果：96[172638496697]第七趟排序结果：6[9172638496697]最后结果序列：69172638496697第二题：69172638496697第一趟排序结果：691726384966[97]第二趟排序结果：6917263849[6697]第三趟排序结果：69172638[496697]第四趟排序结果：691726[38496697]第五趟排序结果：6917[2638496697]第六趟排序

5、结果：69[172638496697]第七趟排序结果：6[9172638496697]最后结果序列：691726384966974、由练习引出(1)、一次冒泡排序的结果：使关键字最大的记录排在了序列的最后一个位置上。(很重要)(2)、冒泡排序的特点：第一，."编程复杂度"很低，很容易写出代码；笫二，具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，(3)、比较两题的题目区别和排序过程区别。第一题是一组逆序数据，每一趟排序都进行了数裾交换，共进行了8-1=7次冒泡；第二题是一组正序数据，进行完一次排序后就发现，没有任何数据交换发生，后谢进行的第二

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

7、好，此时排序可结朿。四、用文字描述冒泡排序算法思考方法：首先是对数组的相邻的两数比较，根据比较结果确定是否交换位罝；这种比较进行的次数比数据列屮数据个数少1;（此两步完成了一次冒泡排序）对一个序列來说，共进行多少次冒泡排序呢？最多和上面第二步的比较次数一样，但也可提前结束，只要在某一遍冒泡中没有发生数据交换即川'。如何确定是否发生数据交换，在程序屮，可以考虑设置一个标志位，当发生数裾交换时，更改标志位，每次重新进行冒泡排序之前可以检查标志位，如果没有发生改变，则可证明上一次冒泡已经没有数据交换发生,也就是说数据序列已经排好，可