数据结构第10章-排序ppt课件.ppt

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

1、数据结构第10章内部排序信息工程学院衷璐洁概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容一、排序的定义假设含n个记录的序列为{R1,R2,…,Rn}其相应的关键字序列为{K1,K2,…,Kn}需确定1,2,…,n的一种排列p1,p2,…,pn，使其相应的关键字满足如下的非递减(或非递增)关系：Kp1≤Kp2≤…≤Kpn即使序列{R1,R2,…,Rn}成为一个按关键字有序的序列{Rp1,Rp2,…,Rpn}这样一种操作称为排序关键字Ki可以是记录Ri的主关键字【排序结果唯一】、次关键字或若干数据项的组合【排序结果不唯一】假

2、设：(1)在待排序序列中存在两个(以上)关键字相等的记录Ri和Rj，即：Ki=Kj(1≤i,j≤n，i≠j)(2)在排序前的序列中Ri领先于Rj(即：i

3、据的不同原则大致可分为：按内部排序过程所需的工作量分：插入排序交换排序选择排序归并排序基数排序(1)简单的排序方法——O(n2)(2)先进的排序方法——O(nlog2n)(3)基数排序——O(d·n)四、内部排序方法(1)比较：比较两个关键字的大小大多数排序都需要(2)移动：将记录从一个位置移到另一个位置可通过改变记录的存储方式避免五、大多数排序的两种基本操作排序时必须移动记录(2)静态链表存储——(链)表排序排序时不移动记录，仅需修改指针(3)顺序存储＋地址向量＝地址排序排序时不移动记录，而是移动地址向量中的“地址”排序结束后再按地址向量中的值调整记录的

4、存储位置六、排序记录的存储方式(1)顺序存储待排记录的数据类型：#defineMAXSIZE20//顺序表的最大长度typedefintKeyType;//关键字类型typedefstruct{KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容一、直接插入

5、排序方法：将一个记录插入到已排好序的有序表中，得到一个新的、记录数增1的有序表：（1）把序列(R(K1))看成是一个有序的子序列把R(K2)插入到该序列中,使插入后序列(R(K1),R(K2))有序（2）把R(K3)插入到(R(K1),R(K2))中，使插入后有序（3）重复（2），直到插入R(Kn)为止。10.2插入排序49，38，65，97，76，13，2749384938496538496597384965769713384965769713273849657697//对顺序表L作直接插入排序的算法voidInsertSort(SqList&L){//

6、算法10.1for(i=2;i<=L.length;++i)//"<"时，需将L.r[i]插入有序子表if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];//复制为哨兵for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//记录后移L.r[j+1]=L.r[0];//插入到正确位置}}//InsertSort[576489]6某趟插入排序:复制为哨兵j89j64j7j6i直接插入排序的时间复杂度：O(n2)二、其它插入排序直接插入排序适合待排序数量n很小的情

7、况，若n很大，则不宜采用为此，从减少“比较”和“移动”这两种操作的次数考虑，可有以下几种排序的方法：(1)折半插入排序(2)2-路插入排序(3)表插入排序(4)希尔排序(1)折半插入排序做法：用折半查找的方法找到插入位置例：在序列{13，27，35，48，65，72}中插入20或603565132748722060//对顺序表L作折半插入排序voidBInsertSort(SqList&L){//算法10.2for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]low=1;high=i-1;whi

8、le(low<=high){//在r[low..high]中折半查