《数据结构》课程教学资源（教案设计）11 快速排序

编号：012 课程 章节 数据结构 第八章内部排序 课程讲 名称 名称 8.3快速（交换）排序 授学时 45分钟 学习要求 知识点 识记理解 熟练 应用 分析 掌握 综合 课堂快速排序的基本思想 教学 快速排序算法及复杂性分析 目的 态度积极主动学习 >熟悉快速排序方法的基本思想及其算法 能力 掌握快速排序方法的时间复杂性分析方法，能从“关键字的比较次 数”分析排序算法的平均情况和最坏情况的时间性能 教学内容（教学过程设计） 教学安排 8.3快速（交换）排序 给出起泡排序算法的基本思想，强调比较的是相邻记录 分饼 根据基本思想运行实例，引导学生提出起泡排序算法需要解决的关键问 带着关键问题重新运行实例，在每一趟排序中进一步提出问题并解决问 将关键问题的解决文宗写出算法，最后给出完整的起泡排序算法。注意 思维方式：算法是从里层向外层写的 5分钟 分析最好、最坏、平均情况下的时间性能 分析空间性能和算法的稳定性 将起泡算法的时间性能与直接插入算法做比较 提出问题：如何改进起泡排序？ 教学提示： >在C语言中一般都介绍过起泡排序，因此，本讲注意不要与C语言所讲 10分钟 的内容重复。本讲介绍的是最快的起泡排序，注意把起泡排序的改进过 程讲出来，强调观察算法的运行实例并正确提出问题是关键。对于起泡 排序算法，注意算法是从里层向外层写的，这体现了一种思维方式，一 10分钟 种写程序和读程序的方法 10分钟 分析起泡排序的排序过程，引出快速排序改进的着眼点

编号：012 课程 名称 数据结构 章节 名称 第八章 内部排序 8.3 快速（交换）排序 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 快速排序的基本思想 √ √ √ √ √ 快速排序算法及复杂性分析 √ √ √ √ √ 态度 积极主动学习 能力 ➢ 熟悉快速排序方法的基本思想及其算法 ➢ 掌握快速排序方法的时间复杂性分析方法，能从“关键字的比较次 数”分析排序算法的平均情况和最坏情况的时间性能 教学内容（教学过程设计） 教学安排 8.3 快速（交换）排序 ↓ 给出起泡排序算法的基本思想，强调比较的是相邻记录 根据基本思想运行实例，引导学生提出起泡排序算法需要解决的关键问 题 带着关键问题重新运行实例，在每一趟排序中进一步提出问题并解决问 题 将关键问题的解决文宗写出算法，最后给出完整的起泡排序算法。注意 思维方式：算法是从里层向外层写的 分析最好、最坏、平均情况下的时间性能 分析空间性能和算法的稳定性 将起泡算法的时间性能与直接插入算法做比较 ↓ 提出问题：如何改进起泡排序？ ↓ 教学提示： ➢ 在 C 语言中一般都介绍过起泡排序，因此，本讲注意不要与 C 语言所讲 的内容重复。本讲介绍的是最快的起泡排序，注意把起泡排序的改进过 程讲出来，强调观察算法的运行实例并正确提出问题是关键。对于起泡 排序算法，注意算法是从里层向外层写的，这体现了一种思维方式，一 种写程序和读程序的方法 ↓ 分析起泡排序的排序过程，引出快速排序改进的着眼点 5 分钟 5 分钟 5 分钟 10 分钟 10 分钟 10 分钟

给出快速排序的基本思想，体会其分治思想 根据基本思想，提出快速排序算法需要解决的关键问题 给出选择轴值的几种方法，为时间性能分析做铺垫 运行一个一次划分的例子，写出一次划分算法 对划分后得到的两个子序列递归处理，写出快速排序算法 用递归树描述快速排序的递归执行过程，强调轴值的位置，分析最好、 最坏、平均情况的时间性能 分析空间性能和稳定性 教学提示： 注意快速排序改进的着眼点，引导学生掌握改进算法的基本出发点 一次划分是快速排序的重点，深刻理解一次划分的思想和过程，引申 次划分的思想解决其他相关问题 时干快速非的间性能，不急干给出结论，先出快速非的递归 树，分析时间性能的决定因素，再给出最好、最坏、平均情况下的时间 性能 重点： （1)快排序算法的基本思想： (2)快速排序算法的执行村程 重点 （3)快速排序算法的设计。 与 雅点： 难点 快速排序算法的时间复杂度的分析， 对策 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目 提出问题，引导学生 积极参与一 一尝试解决问题，在讨论的基础上给出结论一一讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率」 教学 教学方法：导入，配合图形、实例讲解，提问、讨论 方法 教学手段：PPT课件，板书，动画演示 与 手段 作业： 作业 (1)设待排序的关键字序列为(12,2,16,30,28,10,16*，20,6， 及 课外 18},试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态 推荐 @直接插入排序 资 ②折半插入排序

给出快速排序的基本思想，体会其分治思想 根据基本思想，提出快速排序算法需要解决的关键问题 给出选择轴值的几种方法，为时间性能分析做铺垫 运行一个一次划分的例子，写出一次划分算法 对划分后得到的两个子序列递归处理，写出快速排序算法 用递归树描述快速排序的递归执行过程，强调轴值的位置，分析最好、 最坏、平均情况的时间性能 分析空间性能和稳定性 ↓ 教学提示： ➢ 注意快速排序改进的着眼点，引导学生掌握改进算法的基本出发点 ➢ 一次划分是快速排序的重点，深刻理解一次划分的思想和过程，引申一 次划分的思想解决其他相关问题 ➢ 对于快速排序的时间性能，不要急于给出结论，先画出快速排序的递归 树，分析时间性能的决定因素，再给出最好、最坏、平均情况下的时间 性能 重点 与 难点 对策 重点： （1）快排序算法的基本思想； （2）快速排序算法的执行过程； （3）快速排序算法的设计。 难点： 快速排序算法的时间复杂度的分析。 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1）设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6， 18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。 ① 直接插入排序 ② 折半插入排序

③希尔排序（增量选取5,3,1） ④冒泡排序 ⑤快速排序 ⑥简单选择排序 ⑦堆排序 ®二路归并排序 课后导读： Kuth的《程序设计艺术》第3卷—排序和查找，到目前为止仍不失为 一本排序的综合参考文献。在计算机界，很少有一本书的价值与使用价值能保 持如此之久 以单链表做存储结构的直接插入排序算法、改进的折半插入排序算法、简 单选择排序算法请参见《数据结构(C+版)学习辅导与实验指导》（王红梅 清华大学出版社) 初始建堆时间开销的详细分析请参见《数据结构与算法》（许卓群清华大 学出版社) 在静态链表上实现二路归并排序不需要辅助空间，具体算法请参见《数据 结构 C++实现》（穆淮扣科学出版社） 教学 后记

③ 希尔排序（增量选取 5，3，1） ④ 冒泡排序 ⑤ 快速排序 ⑥ 简单选择排序 ⑦ 堆排序 ⑧ 二路归并排序 课后导读： ➢ Knuth 的《程序设计艺术》第 3 卷——排序和查找，到目前为止仍不失为 一本排序的综合参考文献。在计算机界，很少有一本书的价值与使用价值能保 持如此之久 ➢ 以单链表做存储结构的直接插入排序算法、改进的折半插入排序算法、简 单选择排序算法请参见《数据结构（C++版）学习辅导与实验指导》（王红梅 清华大学出版社） ➢ 初始建堆时间开销的详细分析请参见《数据结构与算法》（许卓群 清华大 学出版社） ➢ 在静态链表上实现二路归并排序不需要辅助空间，具体算法请参见《数据 结构——C++实现》（穆淮扣 科学出版社） 教 学 后记