数据结构chapter_10.ppt

《数据结构chapter_10.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第十章排序第十章内部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.2其它插入排序10.2.3希尔排序10.3快速排序10.4选择排序10.4.1简单选择排序10.4.3堆排序10.5归并排序10.6基数排序10.6.1多关键字的排序10.6.2链式基数排序10.7各种内部排序方法的比较讨论10.1概述排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。有序表与无序表：一组记录按关键字的递增或递减次序排列得到的结果被称之为有序表，相应地，把排序前的状态称为无序表。内部排序和外部排序：内部排序：待排序记录存放在内存外部排序：排

2、序过程中需对外存进行访问的排序正序表与逆序表：若有序表是按关键字升序排列的，则称为升序表或正序表，否则称为降序表或逆序表。不失普遍性，一般只讨论正序表。内部排序的方法：插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序其它排序:多关键字排序、基数排序排序基本操作：比较两个关键字大小将记录从一个位置移动到另一个位置排序算法的稳定性:考虑有多个数据元素具有相同关键字的情况。稳定：具有相同关键字的数据元素的相对位置关系在排序前后保持不变。不稳定：具有相同关键字的数据元素的相对位置关系在排序前后发生了

3、改变。待排序记录在内存中怎样存储和处理？顺序排序——排序时直接移动记录；链表排序——排序时只移动指针；地址排序——排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。注：大多数排序算法都是针对顺序表结构的(便于直接移动元素)顺序存储（顺序表）的抽象数据类型如何表示？typedefstruct{//定义每个记录（数据元素）的结构KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{//定义顺序表L的结构RecordTyper[MAXSIZE+1];//存储顺序表

4、的向量//r[0]一般作哨兵或缓冲区intlength;//顺序表的长度}SqList;//顺序表类型#defineMAXSIZE20//设上课举例的记录数均不超过20个typedefintKeyType;//设关键字为整型量（int型）内部排序的算法有哪些？——按排序的规则不同，可分为5类：插入排序交换排序（重点是快速排序）选择排序归并排序基数排序d＝关键字的位数(长度)——按排序算法的时间复杂度不同，可分为3类：简单的排序算法：时间效率低，O(n2)先进的排序算法:时间效率高，O(nlog2n)基数排序算法：时间效率高，O(d×n)例:49386597761327i=238

5、(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：10.2插入排序10.2.1直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。算法参见P265直接插入排序算法的实现：voidInsertSort(SqLi

6、st&L){//对顺序表L作直接插入排序for(i=2;i<=L.length;++i)//直接在原始无序表L中排序if(L.r[i].key

7、//InsertSort（参见教材P265）例1：关键字序列T=（21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。*表示后一个25i=121254925*16080123456哨兵21i=2i=3i=5i=4i=6254925*25*49161625*080849解：假设该序列已存入一维数组r[7]中，将r[0]作为哨兵（Temp）。则程序执行过程为：21254925*21初态：164925*25211608完成!时间效率：因为在最坏情况下，所有元素的比较次数总和为