数据结构第9章 排序

《数据结构第9章 排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9章排序1第9章排序基本概念插入排序交换排序选择排序归并排序基数排序9.1基本概念目的：实现快速查找定义：调整原文件中的记录顺序，使之按关键字递增(或递减)次序排列起来。其形式化定义描述如下：输入：n个记录r1，r2，…，rn，其相应的关键字分别为k1，k2，…，kn输出：rl′，r2′，…，rn′，使得k1′≤k2′≤…≤kn′。(或k1′≥k2′≥…≥kn′)//有序升序或者降序9.1基本概念默认的排序数据结构：#defineMAXSIZE100typedefintKeyType；/*假定关键字类型为整数类型*/typedefstruct{K

2、eyTypekey；/*关键字项*/OtherTypeother；/*其他项*/}DataType；/*数据元素类型*/typedefstruct{DataTyper[MAXSIZE+1]；/*r[0]闲置或充当前哨站*/intlength；/*顺序表长度*/}SqList；/*顺序表类型*/9.1基本概念分类内排序外排序稳定性稳定排序不稳定排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置9.2插入排序基本思想通过构建有序序列，将待排序的数据，在已排好序的序列中从后向前扫描，找到其相应位置并进行插入操作。常见的插入排序算法直接插入排序

3、折半插入排序希尔排序9.2.1直接插入排序voidStraightInsertSort(SqList*S){inti，j；for(i=2；i<=S->length；i++){S->r[0]=S->r[i]；/*复制为哨兵*/j=i-1;while(S->r[0].keyr[j].key){S->r[j+1]=S->r[j]；j--;}/*记录后移*/S->r[j+1]=S->r[0]；/*插入到正确位置*/}}2/89.2.1直接插入排序空间效率：O(1)一个辅助单元r[0]时间效率：最好情况：O(n)最坏情况:O(n2)总的比较次数=次总

4、的移动次数=次一般情况:O(n2)9.2.3希尔排序〖举例〗:8194119612351795285841751596281258813541941775119515步长=596419411285835759512811715步长=3步长=1964194112858357595128117159.2.3希尔排序希尔排序算法描述：（1）选择一个步长序列t1，t2，…ti，…tk，其中ti>ti+1，tk=1；（2）按步长序列个数k，对序列进行k趟排序；（3）每趟排序，根据对应的步长ti，将待排序列分割成若干个子序列，分别对各子序列进行直接插入排序。仅

5、当步长为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。9.2.3希尔排序Shell排序算法描述如下：voidShellInsert(SqList*s，intgap){/*一趟增量为gap的插入排序，gap为步长*/inti,j；for(i=gap+1；i<=S->length；i++)if(S->r[i].keyr[i-gap].key){/*小于时，需将r[i]插入有序表*/S->r[0]=S->r[i]；/*为统一算法设置监视哨*/for(j=i-gap；j>0&&S->r[0].keyr[j].key；j=j-ga

6、p)S->r[j+gap]=S->r[j]；/*记录后移*/S->r[j+gap]=S->r[0]；/*插入到正确位置*/}/*if*/}9.2.3希尔排序Shell排序算法描述如下：voidShellSort(SqList*s，intgaps[]，intt){/*按增量序列gaps[0，1…，t-1]对顺序表S作希尔排序*/intk；for(k=0；k

7、210311412513614715816步长=819210311412513614715816步长=419210311412513614715816步长=212345678910111213141516步长=11：时间复杂度分析问题：O(n1.3)2：如何选取步长，步长最好为质数.9.3交换排序交换排序的思想：通过两两比较待排序记录的关键字，若不满足排序要求，则交换;不断重复比较和交换过程，直到待排序记录满足排序要求为止。交换排序算法冒泡排序快速排序9.3.1冒泡排序算法步骤：待排序记录S={r1,r2…,rn},假设待排序记录长为n第一趟：比较

8、记录r1与r2的关键字，若r1.key>r2.key，则将两个记录交换，紧接着依次比较r2和r3，直至rn-1与rn为止。