数据结构第10章-排序

数据结构第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的主关键字【排序结果唯一】、次关键字或若干数据项的组合【排序结果不唯一】假设：(1)在待排序序列中存在两个(以上)关键字相等的记录Ri和Rj，即：Ki=Kj(1≤i,j≤n，i≠j)(2)在排序前的序列中Ri领先于Rj(即：ij)那么：若排序后Ri仍领先于Rj，则称所用的排序方法是稳定的；否则，称所用的排序方法是不稳定的【对不稳定的排序方法，只需举出一组关键字实例说明其不稳定性即可】二、排序方法的稳定性•按排序过程中涉及存储器的不同，可将排序方法分为两大类：–内部排序：待排序记录存放在计算机随机存储器(内存)中进行的排序过程–外部排序：待排序记录的数量很大，内存一次不能容纳全部记录，还需外存辅助的排序过程三、排序的分类•按排序过程中依据的不同原则大致可分为：按内部排序过程所需的工作量分：–插入排序–交换排序–选择排序–归并排序–基数排序–(1)简单的排序方法——O(n2)–(2)先进的排序方法——O(nlog2n)–(3)基数排序——O(d·n)四、内部排序方法(1)比较：比较两个关键字的大小大多数排序都需要(2)移动：将记录从一个位置移到另一个位置可通过改变记录的存储方式避免五、大多数排序的两种基本操作–排序时必须移动记录(2)静态链表存储——(链)表排序–排序时不移动记录，仅需修改指针(3)顺序存储＋地址向量＝地址排序–排序时不移动记录，而是移动地址向量中的“地址”–排序结束后再按地址向量中的值调整记录的存储位置六、排序记录的存储方式(1)顺序存储待排记录的数据类型：#defineMAXSIZE20//顺序表的最大长度typedefintKeyType;//关键字类型typedefstruct{KeyTypekey;//关键字InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容一、直接插入排序•方法：将一个记录插入到已排好序的有序表中，得到一个新的、记录数增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){//算法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很小的情况，若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;while(low=high){//在r[low..high]中折半查找有序插入的位置m=(low+high)/2;//折半if(LT(L.r[0].key,L.r[m].key))high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区}for(j=i-1;j=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入}}//BInsertSort[576489]246将L.r[i]暂存于L.r[0]89647low6mhigh折半插入排序的时间复杂度：O(n2)low(2)希尔排序又称“缩小增量排序”(DiminishingIncrementSort)希尔排序的基本思想：(1)先将整个待排记录序列分割成若干子序列(2)分别对这些子序列进行直接插入排序(3)待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序增量序列为：5，3，149386597761327491327499776493865132749977649386513274938654997761327384949657697/*对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改：1.前后记录位置的增量是dk，而不是1；2.r[0]只是暂存单元，不是哨兵。当j=0时，插入位置已找到*/voidShellInsert(SqList&L,intdk){//算法10.4for(i=dk+1;i=L.length;++i)//需将L.r[i]插入有序增量子表if(LT(L.r[i].key,L.r[i-dk].key)){L.r[0]=L.r[i];//暂存在L.r[0]for(j=i-dk;j0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];//插入}}//ShellInsert/*按增量序列dlta[0..t-1]对顺序表L作希尔排序*/voidShellSort(SqList&L,intdlta[],intt){//算法10.5for(k=0;kt;++k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort希尔排序的时间是所取“增量”序列的函数，涉及一些数学上的尚未解决的难题概述插入排序快速排序选择排序归并排序基数排序各种内部排序方法的比较讨论本讲主要内容•快速排序是一种借助“交换”进行排序的方法10.3快速排序一、起泡排序（BubbleSort)98765432108765432109一趟排序voidBubbleSort(SqList&L){for(i=1;in;i++){change=FALSE;for(j=1;jn-i+1;j++)if(L.r[j].keyL.r[j+1].key){change=TRUE;L.r[j]L.r[j+1];}if(!change)return;}}共进行n-1趟排序，共进行n(n-1)/2次比较T(n)=O(n2)•快速排序是对起泡排序的一种改进•基本思想：通过一趟排序将待排记录分割成独立的两部分一部分记录的关键字均比另一部分记录的关键字小则再分别对这两部分的记录继续进行排序最后达到整个序列有序二、快速排序（QuickSort)•假设待排序序列为{L.r[s]，L.r[s+1]，…，L.r[t]}首先任意选取一个记录(一般为第一个记录L.r[s])作为枢轴(或支点)(pivot)然后按下述原则重新排列其余记录：将所有关键字比它小的记录都安置在枢轴之前将所有关键字比它大的记录都安置在枢轴之后由此，以该“枢轴”记录最后所落的位置i作分界线，将序列{L.r[s]，L.r[s+1]，…，L.r[t]}分割成两个子序列：{L.r[s]，L.r[s+1]，…，L.r[i-1]}和{L.r[i+1]，L.r[i+2]，…，L.r[t]}这个过程称作一趟快速排序(或一次划分)4938659776132749i27386597761349492738499776136549jiiijjijj2738139776496549iji2738134976976549ij27381376976549jj具体实现：low=s;high=t;pivotkey=L.r[low].key;(1)从high开始往前找第一个关键字小于pivotkey的记录，与枢轴记录交换(2)从low开始往后找第一个关键字大于pivotkey的记录，与枢轴记录交换(3)重复（1）（2）直到low==high为止此时枢轴记录所在的位置i=low=high273813497697654913273849657697/*算法10.6(a)交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其所在位置，此时在它之前(后)的记录均不大(小)于它*/每交换一对记录需进行3次记录移动(赋值)操作！但对枢轴记录的赋值是多余的！只有在一趟排序结束low=high的位置才是枢轴的最后位置，改写该算法！intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;//用子表的第一个记录作枢轴记录while(lowhigh){//从表的两端交替地向中间扫描while(lowhigh&&L.r[high].key=pivotkey)--high;L.r[low]←→L.r[high];//将比枢轴记录小的记录交换到低端while(lowhigh&&L.r[low].key=pivotkey)++low;L.r[low]←→L.r[high];//将比枢轴记录大的记录交换到高端}returnlow;//返回枢轴位置}//Partition//改进后的算法10.6(b)intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录pivotkey=L.r[low].key;//枢轴记录关键字while(lowhigh){//从表的两端交替地向中间扫描while(lowhigh&&L.r[high].key=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端while(lowhigh&&L.r[low].key=pivotkey)++low;L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端}L.r[low]=L.r[0];//枢轴记录到位returnlow;//返回枢轴位置}//Partition//对顺序表L作快速排序//递归形式的快速排序算法//对顺序表L的子序列L.r[low..high]作快速排序voidQSort(SqList&L,intlow,inthigh){if(lowhigh){//长度大于1//将L.r[low..high]一分为二pivotloc=Partition(