安徽新华电脑专修学院课堂教学教案 （电脑应用课使用） 课程名称 数据结构 教学对象 新华软工专业 教 材 数据结构（C语言） 授课内容 第九章 排序 课 时 2 教学目的 与要求 深刻理解排序的定义和各种方法的特点，并加以灵活应用。了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序。掌握各种排序方法的时间复杂度的分析方法。 重点、难点 重点，难点：希尔排序、快速排序、归并排序、基数排序各种内部排序方法的比较讨论。 课 型 电脑＋理论 教学方法 投影、讨论、版书 教学过程 设计 （包括讲授知识、演示内容及案例、提问及学生演示内容） 任务一、排序的基本概念 前言 计算机在进行数据处理工作时，排序是其最基本的运算之一。在当今的计算机系统中，系统的运行时间很大比例花费在排序上。有资料表明，一些商用计算机在排序上的CPU 时间达到 20%至 60%。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。因此，对于计算机专业人员来说，本章介绍的内容是十分重要的，主要内容有插入排序、冒泡排序、快速排序、直接排序、堆排序和归并排序的基本思想、步骤及方法 一、排序介绍 排序（Sorting ）是数据处理中一种很重要的运算，同时也是很常用的运算，一般数据处理工作 25%的时间都在进行排序。简单地说，排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程 表9-1 学生档案表 例如，在表9-1 中，若以每个记录的学号为关键字，按排序码年龄的递增（由小到大）排序，则所有记录的排序结果可简记为： {（99006，16），（99003，17），（99001，18），（99004，18），（99002，19），（99005，20）}； 也可能为： {（99006，16），（99003，17），（99004，18），（99001，18），（99002，19），（99005，20）}； 这两个结果都是表9-1 按年龄的递增排序结果。若按排序码姓名来进行递增排序，则得到的排序结果为： {（99006，李小燕），（99002，林一鹏），（99001，王晓佳），（99003，谢宁），（99004 ，张丽娟），（99005 ，周涛）} 当然，我们还可以按排序码性别来进行递增排序，在此不再作进一步的分析。‘ 二、基本概念 1．排序码（Sort Key） 作为排序依据的记录中的一个属性。它可以是任何一种可比的有序数...
