1 / 15 山 东 轻 工 业 学 院教 师 授 课 教 案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位 : 信息科学与技术学院授课班级：授课教师：杨春花2 / 15 山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第九章内部排序第一节概述排序的定义、稳定性、 、分类和排序表的存储结构表示。第二节插入排序直接插入排序的思想、算法和分析；希尔排序的思想、算法和分析。第三节交换排序冒泡排序的思想、算法和分析；快速排序的思想、算法和分析。第四节选择排序简单选择排序的思想、算法和分析；树形选择排序的思想；堆的定义、筛选法建堆的过程、堆排序的算法和分析。第五节归并排序归并排序的思想、算法和分析。第六节基数排序多关键字排序和链式基数排序。第七节各种内部排序方法的比较讨论各种内部排序方法的比较，内部排序的时间复杂度的下界。目的要求目的：掌握内部排序的基本方法基本要求：理解二路归并排序、堆排序、基数排序的思想和算法，理解各种排序方法的特点；掌握排序的基本概念，掌握直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序的思想和算法。重点希尔排序、冒泡排序、堆排序、快速排序、二路归并排序和基数排序。难点堆排序、快速排序、二路归并排序和基数排序。作业布置习题 10 参考书1. 数据结构题集 (C 语言版 ), 严蔚敏，清华大学出版社，2002。3. 数据结构、算法与应用－C++语言描述， ( 美)Sartaj Sahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分配复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟3 / 15 教学手段板书、课件总结分钟备注共 8 学时，其中2 学时为习题课注：课型一栏填写理论课、实验课、习题课等授课内容备注4 / 15 第 10 章排序10.1 概述为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找效率较高。还有，二叉排序树、B-树和 B+树的构造过程就是一个排序过程。排序 (sorting) 是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按关键码有序的序列。1.排序的定义（1）排序的定义：设{R 1, R2,⋯, Rn} 是由 n 个记录组成的文件，{K 1, K 2,⋯, K n} 是排序码集合，所谓排序是将记录按排序码递增（或递减）的排列。排序码可以是主关键码，也可以是次关键码...
