内部排序1概述2插入排序3快速排序.ppt

该【内部排序1概述2插入排序3快速排序 】是由【相惜】上传分享，文档一共【38】页，该文档可以免费在线阅读，需要了解更多关于【内部排序1概述2插入排序3快速排序 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。{r1,r2,?,rn},对应的关键字序列为{k1,k2,?,kn},需确定一种关系p(1),p(2),?,p(n)使得关键字序列满足:kp1?kp2???kpn或者kp1?kp2???kpn即使记录成为一个按关键字有序的序列{rp1,rp2,?,rpn}这一过程称为排序。,如果任意两个关键字相同的记录,用某种排序方法排序后相对位置不变,那么称这种排序方法是稳定的,否那么称为不稳定的。设49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——稳定排序后:13,27,38,49,49,65,76,97——:考虑一种股票交易1〕顾客输入:股东帐号、股票代码、申购价格、数量,股票交易系统将用户申购请求插入申购队列队尾;2〕股票交易系统按如下原那么交易:A〕申购价高者先成交B〕申购价相同者按申购时间先后顺序成交例申购队列:用线性表表示交易前:将申购队列按申购价排序,显然为满足原则交易(B),要求排序方法是稳定的申购队列(09,10),(06,),(033,),(051,10)排序后:(06,),(09,10),(051,10),(033,)①待排记录放于地址连续的存储单元中;②待排记录放于链表,记录之间的次序关系由指针指示。③待排记录存放在地址连续的存储单元中,同时另设一个指示各个记录存储位置的地址向量。#defineMAXSIZE20//顺序表的最大长度typedefintKeyType;//定义关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作监视哨intlength;//顺序表长度}SqList;//:每步将一个待排序的对象,按其关键码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。插入排序有多种具体实现算法:1)直接插入排序2):将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……整理ppt解决方法:将第1个记录看成是初始有序表,然后从第2个记录起依次插入到这个有序表中,直到将第n个记录插入。关键问题(1)如何构造初始的有序序列?:for(i=2;i<=;++i){…}整理ppt