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

《内部排序1概述2插入排序3快速排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构10.1概述第十章内部排序10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较10.1概述一.排序的定义假设含有n个记录的序列{r1,r2,,rn},对应的关键字序列为{k1,k2,,kn},需确定一种关系p(1),p(2),,p(n)使得关键字序列满足：kp1kp2kpn或者kp1kp2kpn即使记录成为一个按关键字有序的序列{rp1,rp2,,rpn}这一过程称为排序。二.排序的稳定性在待排记录序列中，如果任意两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳

2、定的，否则称为不稳定的。设49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——稳定排序后:13,27,38,49,49,65,76,97——不稳定例10.1概述排序稳定性的应用股票交易系统：考虑一种股票交易1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；2）股票交易系统按如下原则交易：A）申购价高者先成交B）申购价相同者按申购时间先后顺序成交例申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足原则交易(B)，要求排序方法是稳定的申购队列（09,10),(06

3、,10.5),(033,9.8),(051,10)排序后：(06,10.5),(09,10),(051,10),(033,9.8)实现10.1概述①待排记录放于地址连续的存储单元中；②待排记录放于链表，记录之间的次序关系由指针指示。③待排记录存放在地址连续的存储单元中，同时另设一个指示各个记录存储位置的地址向量。三.待排记录序列的存储方式10.1概述四.顺序存储结构表示待排记录#defineMAXSIZE20//顺序表的最大长度typedefintKeyType;//定义关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeother

4、info;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作监视哨intlength;//顺序表长度}SqList;//顺序表类型10.1概述10.2插入排序思路：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。插入排序有多种具体实现算法：1)直接插入排序2)希尔排序一.直接插入排序10.2插入排序思路：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。有序序列无序序列r1r2ri-1rirnri+1…………r'1

5、r'2r'i-1r'i……rnri+1……解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。关键问题(1)如何构造初始的有序序列？一.直接插入排序10.2插入排序算法描述：for(i=2;i<=L.length;++i){…}关键问题(2)如何查找待插入记录的插入位置?解决方法：在i-1个记录的有序区r[1]~r[i-1]中插入记录r[i]，首先顺序查找r[i]的正确插入位置，然后将r[i]插入到相应位置。一.直接插入排序10.2插入排序算法描述：L.r[0]=L.r[i];for(j=i-1;L.r[0].key

6、j].key;--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];例初始关键字4938659776132749()i=23849659776132749()(38)i=33849659776132749()(65)i=43849659776132749()(97)i=81327384949657697()(49)i=53849657697132749()(76)i=61338496576972749()(13)i=71327384965769749()(27)算法：voidInsertSort(SqList&L){for(i=2;i<=L.length;++

7、i)//只有一个元素也是有序表if(L.r[i].key