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

刘建科++冯媛媛

摘要：快速排序算法是基于关键字比较的一种内排序，其算法思想抽象，文章分析了教学中存在的问题，提出了先讲典型案例，再去理解算法思想的教学方法，从而促进学生对抽象算法思想的理解和掌握，提高了课堂教学效率。

关键词：快速排序；教学要点

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2016）17-0117-02

排序是将一个数据元素（或记录）的任意系列重新排成一个按关键字有序序列。快速排序作为内排序的一种，在所有同数量级（Ologn）排序方法中，其平均性能（时间复杂度、空间复杂度）优于其它内排序方法。

快速排序的算法思想：通过一趟排序将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两个部分记录继续进行排序，直到整个序列有序。

1 快速排序算法在教学中存在的问题

算法思想内容过于抽象，理解困难，不易掌握。学生一般在看到快速排序的算法思想时，一时很难弄明白，也很难理解。单一从文字叙述方面来弄懂快速排序算法思想很困难，如果我们换个思路，先看具体案例，再来理解算法，就会发现该算法思想其实并不难理解。

在待排序的n个记录中任取一个记录（通常取第一个记录）作为枢轴，把该记录放入最终位置后，数据序列被此记录分割成两部分。所有关键字比该记录关键字小的记录放置在前一部分，所有比它大的记录放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一趟快速排序。

下面通过例子来说明快速排序的算法思想：

例：设记录关键字集合key={49，38，66，90，75，10，20}。请写出快速排序第一趟之后的状态。

图1 一趟快速排序

一趟排序之后的状态：{20 38 10 49 75 90 66}。

我们可以把一次交换分成两个步骤：一是从右向左查找第一个小于关键字的记录，找到并交换位置；二是从左向右查找第一个大于关键字的记录，找到并交换位置；完成一趟快速排序，一般情况下需要多次交换，直到满足排序结束的条件：“在一趟排序过程中没有进行过交换记录的操作”。

一趟快速排序后记录关键字集合被划分为两个部分，然后分别对这两部分进行快速排序：

2 快速排序算法的不足之处

快速排序算法有两点不足，一是若初始记录序列按关键字有序或基本有序时，速度反而最慢；二是排序结果不稳定。

在所有同数量级O（nlogn））的排序方法中，快速排序被认为平均性能最好，但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化起泡排序，其时间复杂度O（n2）。

3 方法探讨

由于数据结构课程内容繁多、理论抽象、逻辑性强、难以理解等特点，造成教师教学费力，学生学习吃力，教学效果不理想，教师在教学内容的选择方面，存在“重理论，轻实践”的普遍现象。目前部分教师仍采用传统教学方法——“满堂灌”（讲授法），忽略了学生的主体地位，在讲授理论的同时，不观察学生的听课反映，未给学生留出思考时间，缺少与学生的互动环节，这样可能学生跟不上老师的思路， 降低了听课效率。

针对教学中存在的问题，提出如下建议：

（1）采取案例教学，激发学习兴趣

案例教学法具有较强沟通性、针对性、实践性等特点。课堂教学中运用案例教学法，将理论知识融入案例之中，运用案例引导学生主动学习，激发学习兴趣。案例教学法的核心——案例必须是优选的。好的案例对于学生掌握基本概念、基本知识，培养基本技能起到积极的推动作用。

（2）理论联系实际，做好上机实验

学习算法，不仅要理解教材上的理论知识，更重要的是能够联系实际，能针对实际问题编写出正确易读、结构清晰、执行效率高的程序，上机实验也是学习数据结构必不可少的教学环节，对于训练学生编程能力，加深抽象理论的理解至关重要。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].

[2] 叶振，李小波.地方性院校数据结构课程教学探索[J].电脑知识与技术，2015（26）.

[3] 陈燕，屈莉莉，李桃迎.数据结构课程难点讲授方法与必备知识[J].教育教学论坛，2015（27）.