快速排序算法的教学要点与方法探讨.doc

快速排序算法的教学要点与方法探讨.doc快速排序算法的教学要点与方法探讨摘要:快速排序算法是基于关键字比较的一种内排序,其算法思想抽象,文章分析了教学中存在的问题,提出了先讲典型案例,再去理解算法思想的教学方法,从而促进学生对抽象算法思想的理解和掌握,提高了课堂教学效率。关键词:快速排序;教学要点中图分类号::A文章编号:1009-3044(2016)17-0117-02排序是将一个数据元素(或记录)的任意系列重新排成一个按关键字有序序列。快速排序作为内排序的一种,在所有同数量级(Ologn)排序方法中,其平均性能(时间复杂度、空间复杂度)优于其它内排序方法。快速排序的算法思想:通过一趟排序将待排序记录分割成独立的两个部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两个部分记录继续进行排序,直到整个序列有序。1快速排序算法在教学中存在的问题学生一般在看到快速排序的算法思想时,一时很难弄明白,也很难理解。单一从文字叙述方面来弄懂快速排序算法思想很困难,如果我们换个思路,先看具体案例,再来理解算法,就会发现该算法思想其实并不难理解。算法思想内容过于抽象,理解困难,不易掌握。Si在待排序的n个记录中任取一个记录(通常取第一个记录)作为枢轴,把该记录放入最终位置后,数据序列被此记录分割成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一趟快速排序。下面通过例子来说明快速排序的算法思想:例:设记录关键字集合key={49,38,66,90,75,10,20}。请写出快速排序第一趟之后的状态。图1一趟快速排序一趟排序之后的状态:(20381049759066}□我们可以把一次交换分成两个步骤:一是从右向左查找第一个小于关键字的记录,找到并交换位置;二是从左向右查找第一个大于关键字的记录,找到并交换位置;完成一趟快速排序,一般情况下需要多次交换,直到满足排序结束的条件:“在一趟排序过程中没有进行过交换记录的操作”。一趟快速排序后记录关键字集合被划分为两个部分,然后分别对这两部分进行快速排序:2快速排序算法的不足之处快速排序算法有两点不足,一是若初始记录序列按关键字有序或基本有序时,速度反而最慢;二是排序结果不稳定。在所有同数量级O(nlogn))的排序方法中,快速排序被认为平均性能最好,但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化起泡排序,其时间复杂度0(n2)。3方法探讨由于数据结构课程内容繁多、理论抽象、逻辑性强、难以理解等特点,造成教师教学费力,学生学习吃力,教学效果不理想,教师在教学内容的选择方面,存在“重理论,轻实践”的普遍现象。目前部分教师仍采