文档介绍：数据结构课程的内容*一、教学内容:1、插入排序(直接插入排序、折半插入排序、希尔排序)2、交换排序(起泡排序、快速排序);3、选择排序(直接选择排序、堆排序);4、归并排序;5、基数排序;第10章内部排序*二、教学要求:1、了解:各种方法的排序过程及其依据的原则;“表排序”和“地址排序”的过程及其适用场合;基数排序方法及其性能分析方法2、理解:排序方法“稳定”或“不稳定”的过程及其适用场合;排序的定义和各种排序方法的特点并能加以灵活应用。:插入排序、交换排序、选择排序、归并排序的方法及其时间复杂度的分析方法,并能加以灵活应用*重点:希尔排序、快速排序、堆排序、归并排序等排序过程;各种排序方法的时间复杂度的分析方法。难点:各种排序方法的时间复杂度的分析方法。排序方法“稳定”或“不稳定”的过程及其适用场合。*?将一组杂乱无章的数据按一定的规律顺次排列起来。存放在数据表中按关键字排序定义:设有记录序列:{R1、R2………Rn}其相应的关键字序列为:{K1、K2………Kn};若存在一种确定的关系:Kx<=Ky<=…<=Kz则将记录序列{R1、R2……….Rn}排成按该关键字有序的序列:{Rx、Ry……….Rz}的操作,称之为排序。*??时间效率:排序速度(即排序所花费的全部比较次数)空间效率:占内存辅助空间的大小稳定性:若两个记录A和B的关键字值相等,且排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。(凡存在非相邻两个记录进行交换的算法均为不稳定算法)——便于查找!*?什么叫外部排序?若待排序记录都在内存中,称为内部排序;若待排序记录一部分在内存,一部分在外存,则称为外部排序。注:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。*大多数排序算法都有两个基本的操作:关键字的比较:记录的移动5、记录序列的存储方式:顺序存储静态链表地址向量*注:大多数排序算法都是针对顺序表结构的(便于直接移动元素)(顺序表)的抽象数据类型如何表示?typedefstruct//定义每个记录(数据元素)的结构{KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{//定义顺序表的结构RedTyper[MAXSIZE+1];//存储顺序表的向量//r[0]一般作哨兵或缓冲区intlength;//顺序表的长度}SqList;//排序顺序表类型#defineMAXSIZE10//设记录不超过10个typedefintKeyType;//设关键字为整型量(int型)*?——按排序的规则不同,可分为5类:插入排序交换排序(重点是快速排序)选择排序归并排序基数排序d=关键字的位数(长度)——按排序算法的时间复杂度不同,可分为3类:简单的排序算法:时间效率低,O(n2)先进的排序算法:时间效率高,O(nlog2n)基数排序算法:时间效率高,O(d×n)*