数据结构授课教案-第9章内部排序

《数据结构授课教案-第9章内部排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第九章内部排序第一节概述排序的定义、稳定性、、分类和排序表的存储结构表示。第二节插入排序直接插入排序的思想、算法和分析；希尔排序的思想、算法和分析。第三节交换排序冒泡排序的思想、算法和分析；快速排序的思想、算法和分析。第四节选择排序简单选择排序的思想、算法和分析；树形选择排序的思

2、想；堆的定义、筛选法建堆的过程、堆排序的算法和分析。第五节归并排序归并排序的思想、算法和分析。第六节基数排序多关键字排序和链式基数排序。第七节各种内部排序方法的比较讨论各种内部排序方法的比较，内部排序的时间复杂度的下界。目的要求目的：掌握内部排序的基本方法基本要求：理解二路归并排序、堆排序、基数排序的思想和算法，理解各种排序方法的特点；掌握排序的基本概念，掌握直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序的思想和算法。重点希尔排序、冒泡排序、堆排序、快速排序、二路归并排序和基数排序。难点堆排序、快速排序、

3、二路归并排序和基数排序。作业布置习题10参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分配复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共8学时，其中2学时为习题课注：课型一栏填写理论课、实验课、习题课等授课内容备注第10章排序10.1概述为了便于查找，通常希望计算机中的数据表是按关键码有序的。如有序表的折半查找，查找

4、效率较高。还有，二叉排序树、B-树和B+树的构造过程就是一个排序过程。排序(sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按关键码有序的序列。1.排序的定义（1）排序的定义：设{R1,R2,…,Rn}是由n个记录组成的文件，{K1,K2,…,Kn}是排序码集合，所谓排序是将记录按排序码递增（或递减）的排列。排序码可以是主关键码，也可以是次关键码。（2）稳定性假设Ki=Kj(1≤i,j≤n,i¹j)，且在排序前的序列中Ri领先于Rj(即i

5、仍领先于Rj，则称所用的排序方法是稳定的，否则是不稳定的。（3）排序的分类：待排序的记录在排序过程中全部存放在内存的称为内排序，如果排序过程中需要使用外存的称为外排序。按排序原则，排序分为：①插入排序；②选择排序；③交换排序④分配排序⑤归并排序⑥外部排序按排序所需的工作量，排序分为：①简单排序方法，其时间复杂度为O(n2)；②先进的排序方法，其时间复杂度为O(nlogn)；③基数排序，其时间复杂度为O(d·n)；（4）排序中的基本操作：①比较关键码大小②移动记录（5）对于待排序的记录序列，有三种常见的存储表示方法。

6、①向量结构，即将待排序的记录存放在一组地址连续的存储单元中。②链表结构。③记录向量与地址向量结合，即将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。为简单起见，数据的存储结构采取向量的存储结构：#definen20//记录数typedefintkeytype;typedefstruct{keytypekey;datatypeother;}rectype;rectyper[n+1];（6）排序算法的评价：①算法的执行时间②算法执行时所需的附加空间10.2插入排序基本原理：每步将一个

7、待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。10.2.1直接插入排序1直接插入排序的基本思想先假定第1个记录为有序序列，然后从第2条记录开始，依次将记录插入到前面已经有序的序列中，直至全部记录有序。一般情况下，第i趟直接插入排序：将r[i]插入到已经有序的序列r[1..i-1]中，使其变成有序序列r[1..i]。整个排序进行n-1趟插入。2示例：初始：[49]386597761327493算法：voidInsertSort(rectypeR[],intn){inti

8、,j;for(i=2;i