《数据结构与算法(C语言版)》教学参考模块8.docx

模块8排序
教学要求:
(1) 了解排序的概念。
(2)掌握直接插入排序和二分插入排序。
(3)掌握快速排序法。
(4)掌握选择排序法。
(5)掌握归并排序法，并知道各种排序法的优缺点。
教学重点：
插入排序；交换排序；选择排序；归并排序；基数排序；外部排序；各种排序方法的性能比拟。
教学难点：
希尔排序；堆排序；归并排序；基数排序；外部排序。
课时安排：
本章安排6课时。其中，理论讲授4课时，上机实验2课时。
教学大纲：
模块8排序
案例导入
案例分析
相关知识
8. 1概述
8.2 插入排序
8. 2. 1直接插入排序
9. 2.2二分插入排序
10. 2.3希尔排序
8.3 快速排序
8. 3. 1冒泡排序
9. 3.2快速排序
8.4 选择排序
8. 4.1简单项选择择排序
9. 4.2树形选择排序
10. .3堆排序
8. 5归并排序
8.6各种排序方法的比拟
案例实施
案例总结
思考与练习主要概念:
1 .排序.稳定排序法
2 .非稳定排序法.内部排序
3 .外部排序.内部排序的分类
4 .外部排序的基本操作.插入排序
5 .直接插入排序.希尔排序
6 .交换排序.冒泡排序
7 . 一趟冒泡.快速排序
8 .选择排序.简单项选择择排序
9 .堆.大根堆
10 .小根堆.堆排序
11 .筛选.归并
12 .归并排序.二路归并排序
13 .基数排序（桶排序或箱排序）.最高优先位关键字
14 .最低优先位关键字.最高位优先法（MSD）
15 .最低位优先法（LSD）.链式基数排序
16 .外部排序. 2-路平衡归并
17 . b路平衡归并实验：
实验 快速排序算法的实现（2学时）本书附录上机实验7；