内部排序.ppt

1第10章 内部排序o主要内容：主要内容：o排序的基本概念o插入排序o交换排序o选择排序o归并排序o各种排序方法的比较210.1 概述o1.基本概念o排序排序：将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列的过程叫排序。n设序列R1,R2,Rn，相应关键字序列为 K1,K2,Kn，所谓排序是指重新排列 R1,R2,Rn 为 Rp1,Rp2,Rpn，使得满足：Kp1Kp2 Kpn 或 Kp1Kp2 Kpno排序的稳定性排序的稳定性：假设Ki iKj，(1i in;1jn;i ij)且在排序前的序列中Ri i领先于Rj，如在排序后Ri i仍领先于Rj，则称所用的排序方法是稳定稳定的，反之则称排序方法是不稳定不稳定的。32.排序的分类o待排序记录所在位置n内部排序：待排序记录存放在内存中n外部排序：排序过程中需对外存进行访问的排序内部排序适用于记录个数不很多的小文件；外部排序则适用于记录个数太多，不能一次将其全部放入内存的大文件o排序依据策略n插入排序：直接插入排序,折半插入排序,希尔排序n交换排序：冒泡排序,快速排序n选择排序：简单选择排序,堆排序n归并排序：2-路归并排序n基数排序 43.排序的基本操作o排序的基本操作：n比较操作：比较两个关键字的大小n改变指向记录的指针(逻辑关系)或将一个记录从一个位置移动到另一个位置54.数据的存储形式o待排记录一般有三种存储形式n存放在一组地址连续的存储单元中，类似顺序表o实现排序必须借助移动记录n存放在静态链表中o实现排序只需修改指针n存放在一组地址连续的存储单元中，同时另设一个指示各个记录存储位置的地址向量o实现排序时修改地址向量中的地址，排序结束时统一调整记录的存储位置6顺序存储结构定义#define MAXSIZE 20 /顺序表的长度typedef int KeyType;/关键字类型为整数类型typedef struct KeyType key;/关键字项 InfoType otherinfo;/其它数据项RedType;/记录类型type struct RedType rMAXSIZE+1;/r0空作为哨兵 int length;/顺序表长度SqList;/顺序表类型 75.算法复杂度分析o评价排序算法的标准：n执行时间n所需辅助空间n稳定性排序所需时间简单排序：T(n)=O(n2)先进的排序：T(n)=O(logn)基数排序：T(n)=O(d.n)o排序算法的时间开销n主要是关键字的比较次数和记录的移动次数。n有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。o排序算法的空间开销n若所需辅助空间不依赖于问题的规模n，即辅助空间为O(1)，则称为就地排序就地排序。n非就地排序所要求的辅助空间一般为O(n)810.2 插入排序o1.插入排序的基本思想o基本思想：设R=R1，R2，Rn为原始序列，R=初始为空。插入排序就是依次取出R中的元素Ri，然后将Ri有序地插入到R中。o例如：R=5,2,10,2 R=有序插入R=2,10,2R=5R=10,2 R=2,55R=2 2R=2,5,10R=10R=2,2,5,10292.直接插入排序o排序过程：整个排序过程为n-1趟插入n将序列中第1个记录看成是一个有序子序列n从第2个记录开始，逐个进行插入，直至整个序列有序R1R2RnR=R1R=R2，R3，Rn o若R1.i i-1为有序区，寻找Ri i插入位置的方法:n在R0处设置监视哨，即令：R0=Ri in从j=i i-1的记录位置开始依次向前比较n若Ri i.keyRj.key，Rj后移，否则插入位置找到，将Ri i插入到第j+1个位置10算法程序viod Dinsertsort(Sqlist&L)for(i=2;i=L.length;+i)/对每一个RiR /小于时，需将L.ri插入到有序表 if LT(L.ri.key,L.ri-1.key)L.r0=L.ri;/复制为哨兵 /*寻找插入位置j*/for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;/将ji-1的记录后移一格 L.rj+1=L.r0;/将Ri插入到位置j+1 11算法效率o时间复杂度n待排序记录按关键字从小到大排列(正序)比较次数:移动次数:n待排序记录按关键字从大到小排列(逆序)比较次数:移动次数:n待排序记录随机，取平均值比较次数:移动次数:n总的时间复杂度:T(n)=O(n2)o空间复杂度：S(n)=O(1)123.折半插入排序o排序过程：用折半查找方法确定插入位置。o举例：i=1:(49)38 65 97 76 13 27 49(38)LMHHLMi=2:(38 49)65 97 76 13 27 49(65)LMHLMHMHLi=8:(13 27 38 49 49 65 76 97)H+1:插入位置H+1:插入位置13算法程序void BInsertSort(Sqlist&L)for(i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high)/折半查找位置 m=(low+high)/2;if(L.r0.key=high+1;-j)L.rj+1=L.rj;L.rhigh+1=L.r0;算法效率 时间复杂度(只改善了比较):T(n)=O(n2)空间复杂度:S(n)=O(1)折半插入排序是稳定的排序144.希尔排序o希尔排序(Shells Sort)又称“缩小增量排序”，基本思想为：把一个较长的待排序列分成若干段，n=n1+n2+nk；然后，分别对各段进行直接插入排序，使得整个序列基本有序；最后对整个序列进行一次直接插入排序。o希尔排序过程：先取一个正整数间隔d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2ri i+1.key(i i=1,2,n)，则交换(第一趟冒泡排序)，结果关键字最大的记录被放在rn。n在n-1个记录中，若ri i.keyri i+1.key(i i=1,2,n-1)，则交换，结果关键字次大的记录被安置在rn-1n以此类推，直到“在一趟排序过程中没有进行过交换记录的操作”为止r1r2r3rn-1rn第1趟冒泡排序第2趟冒泡排序第n-2趟冒泡排序第n-1趟冒泡排序19算法程序void Bubble_sort(Sqlist&L)for(i=L.length;i1;-i)exchange=false;/设置开关 for(j=1;ji;+j)if GT(L.rj.key,L.rj+1.key)/一趟冒泡 L.rj L.rj+1;/移动3次 exchange=true;if(!exchange)exit;20性能分析o时间复杂度n最好情况(正序)：比较1趟n-1次，不移动n总的时间复杂度：O(n2)o空间复杂度：S(n)=O(1)o冒泡排序是稳定的排序o比较次数：o移动次数：n最坏情况(逆序)：212.快速排序o基本思想：选择一个枢轴，通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录进行排序，以达到整个序列有序。o排序过程：n设序列为r1,r2,rn，定r1为枢轴n设low,high指针分别从两端与枢轴比较，把比r1小的记录放前，比r1大的记录放后，得到一次划分：rs1,rs2,rsk,r r1,rt1,rt2,rtjn然后分别对两序列rs和rt再进行划分,直到划分后的序列剩一个元素为止，这是一个递归的过程22一趟分割过程o先从high所指记录向前搜索，找到第1个小于key的记录与枢轴交换。然后从low起向后搜索，找到第一个比key大的记录与low互换。重复上面两步，直到low=high为止(该位置即为枢轴的位置)4938659776132749初始关键字L1次交换之后2次交换之后3次交换之后4次交换之后完成一趟排序HH2738659776134949HLLL2738499776136549LHH2738139776496549HLL2738134976976549LHHH2738134976976549THANK YOUSUCCESS2024/4/18 周四23可编辑24第1趟排序后2738134976976549快速排序整个过程初始关键字4938659776132749第2趟排序后1327384949657697第3趟排序后1327384949657697有序序列132738494965769749277649结束结束结束结束快速排序是不稳定的排序初始关键字3849659776132749有序序列132738494965769725int Partition(Sqlist&L,int low,int high)/以L.rlow为主记录，对子系列L.rlow.high的一趟划分 temp=L.rlow;while(lowhigh)/进行一趟划分 while(low=temp.key)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=temp.key)+low;L.rhigh=L.rlow;L.rlow=temp;/找到主记录的位置low return low;void Qsort(Sqlist&L,int low,int high)/递归算法实现 if(lowhigh)/长度大于1 loc=Partition(L,low,high);/将L.rlow.high一分为二 Qsort(L,low,loc-1);/对低子表递归排序 Qsort(L,loc+1,high);/对高子表递归排序void QuickSort(SqList L)/对顺序表L做快速排序 Qsort(L,1,L.length);26算法效率分析o时间复杂度n最好情况：每次总是选到中间值作枢轴，则形成二叉递归树：T(n)=O(nlog2n)n最坏情况：每次总是选到最小或最大元素作枢轴，则退化为冒泡排序：T(n)=O(n2)n平均时间复杂度：Tavg(n)=kn ln n；k为某个常数n经验证明，在所有同数量级O(nlogn)的此类排序中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序是速度最快的排序n若枢轴记录取rlow、r(low+high)/2和rhigh中关键字的中值的记录，并与rlow互换，可以大大改善最坏情况的快速排序o空间复杂度：使用栈空间实现递归n最坏情况：S(n)=O(n)；一般情况：S(n)=O(log2n)2710.4 选择排序o基本思想：每一趟在n-i+1(i=1,2,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。o1.简单选择排序o排序过程：n设待排序列为：a1,a2,ann在a1,a2,an中，找最小值记录与a1交换n在a2,a3,an中，找最小值记录与a2交换n重复上述操作，共进行n-1趟排序后，排序结束 o简单选择排序是不稳定的排序551231235528算法程序和效率分析o时间复杂度n移动次数：最好(正序):0；最坏(逆序):3(n-1)n比较次数：void Selectsort(Sqlist&L)for(i=1;iL.length;+i)for(j=i+1,k=i;jL.rj.key)k=j;if(k!=i)L.ri L.rk;n总的时间复杂度：T(n)=O(n2)o空间复杂度：S(n)=O(1)292.堆排序o(1)堆和堆排序o堆堆：n个元素的序列(a1,a2,an)，其关键值序列为：(k1,k2,kn)，当且仅当其关键值满足下式称之为堆：或o满足前一表达式的堆称为小顶堆小顶堆，即堆顶元素为所有元素中最小值；符合后一组不等式的堆称为大顶大顶堆堆，即堆顶元素为所有元素中最大值。考虑完全二叉树的顺序存储，若将其解释成堆如何？30举例o3,7,4,9,10,8，96,83,27,38,11,9374910896832738119小顶堆大顶堆o堆是具有如下性质的完全二叉树：若树中每个结点的值都小于等于(或大于等于)其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。注意：小顶堆中较小结点靠近根结点，但不绝对。大顶堆中较大结点靠近根结点，但也不绝对31堆排序o堆排序堆排序：将无序序列建成一个堆，得到关键字最小(或最大)的记录；输出堆顶的最小(大)值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程就叫堆排序。o排序过程(小顶堆)n若a1，a2，an为堆，则a1最小，交换a1，an，输出ann将剩余a1，a2，an-1调整为堆，当作新的序列n重复这个过程直到序列只剩一个元素32(2)建立堆o算法描述(小顶堆)n首先把给定序列看成是一棵完全二叉树n从第i=结点(最后一个非终端结点)开始与其子树结点比较，若其直接子树结点中较小者小于i结点，则交换。若该直接子树结点交换后大于其孩子结点，继续交换，直到叶结点或不再交换k1k2k3 ki knkiknk2k3k1n令i=i-1，重复前面的过程直到i=1，即到第1个结点为止33举例:9 2 6 1 8 3926183i2i19 2 6 1 8 3 639 2 3 1 8 6219 1 3 2 8 61 91 9 3 2 8 6291 2 3 9 8 612986319286391286392186334(3)调整堆筛选o筛选筛选：输出堆顶元素后，剩余元素重新调整为堆的过程。o调整步骤(小顶堆)n将该完全二叉树中最后一个元素替代已输出的结点n若新的完全二叉树的根结点小于左右子树的根结点，则直接输出。反之，则比较左右子树根结点的大小。若左子树的根结点小于右子树的根结点，则将左子树的根结点与该完全二叉树的根结点交换，否则将右子树与其交换。n重复上述过程，调整左子树(或右子树)，直至叶子结点，则新的二叉树满足堆的条件。35举例123986623981263981863921368921968321698321896321123986 16623981622639812886392183368921968321693969832168896321堆排序的过程就是一个不断从堆顶到叶子的筛选过程8936算法程序void Heapadjust(Sqlist&H,int s,int m)/除结点H.rs外,H.rs+1.m为大顶堆,将s结点调整到适当位置 temp=H.rs;for(j=2*s;j=m;j*=2)/沿k值较大的孩子筛选 if(j0;-i;)Heapadjust(H,i,H.length);/建立初始堆 for(i=H.length;i1;-i;)H.r1 H.ri;/输出第i个小元素 Heapadjust(H,1,i-1);/剩余1.i-1个元素调整为堆37算法效率分析o时间复杂度n对深度为k的堆，筛选算法中进行关键字的比较次数至多为2(k-1)。建堆时，n个元素所需的比较次数不超过4n。总的比较次数：n在最坏情况下，其时间复杂度为O(n log n)o空间复杂度n仅需一个记录大小的辅助存储空间。o堆排序是不稳定的排序。堆排序的运行时间主要耗费在建立初始堆和筛选上，当记录较少时，不值得提倡。当n很大时效率高，是常用算法。3810.5 归并排序o基本思想：将若干有序序列逐步归并，最终得到一个有序序列。o归并归并：将两个或两个以上的有序表合并成一个新的有序表的过程。归并排序有多路归并排序、两路归并排序,可用于内排序，也可以用于外排序。o2-2-路归并排序路归并排序n设初始序列含有n个记录，看成n个有序的子序列，每个子序列长度为1n两两合并，得到 个长度为2或1的有序子序列n对n/2个有序表两两合并，得到n/4个长度为4或3的有序表n重复这个过程，直至得到一个长度为n的有序序列39举例o已知某序列为49,38,65,97,76,13,27，试采用归并排序，将其按从小到大顺序排列。49初始关键字3865977613277个序列381趟归并后4965971376274个序列382趟归并后4965971327762个序列133趟归并后2738496576971个序列40void Merge(RcdType SR,RcdType TR,int i,int m,int n)/将有序序列SRi.m和SRm+1.n归并为有序序列TRi.n for(j=m+1,k=i;i=m&j=n;+k)if(SRi.key=SRj.key)TRk=SRi+;else TRk=SRj+;if(i=m)TRk.n=SRi.m;/将剩余元素复制到TR中 if(j=n)TRk.n=SRj.n;void MSort(RcdType SR,RcdType&TR1,int s,int t)/将SRs.t归并到TR1s.t中 if(s=t)TR1s=SRs;/子序列长度为1 else m=(s+t)/2;/将SRs.t平分成SRs.m和SRm+1.t MSort(SR,TR2,s,m);MSort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);void MergeSort(SqList&L)/对顺序表作归并排序 MSort(L.r,L.r,1,L.length);41算法效率o时间复杂度n对任意两个有序序列，长度分别为 m，n，可以在O(m+n)时间内完成有序归并，因此每趟归并的时间复杂度为O(n)，整个算法需log2n趟。总的时间复杂度：O(n log2 n)o空间复杂度nS(n)=O(n)o归并排序是稳定的排序归并排序算法虽简单，但占用辅助空间大，实用性差4210.7 各种内部排序方法的比较排序方法插入排序冒泡排序简单选择排序希尔排序快速排序堆排序归并排序基数排序平均时间O(n2)O(n2)O(n2)O(n2)O(n log n)O(n log n)O(n log n)O(d(n+rd)最坏情况O(n2)O(n2)O(n2)O(n2)O(n2)O(n log n)O(n log n)O(d(n+rd)辅助空间O(1)O(1)O(1)O(1)O(log n)O(1)O(n)O(rd)稳定性稳定稳定不稳定不稳定不稳定不稳定稳定稳定43总结o从平均时间看，快速排序最佳，所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比较，在n较大时，归并排序所需时间较堆排序省o简单排序中，直接插入最简单，当序列基本有序或n较小，其最佳 o基数排序的时间复杂度可写成O(dn)，它最适用于n值很大而关键字较小的序列o从稳定性来比较，基数排序是稳定的，一般来说，时间复杂度为O(n2)的简单排序也是稳定的，而快速排序、堆排序和希尔排序等时间性能较好的排序方法是不稳定的 THANK YOUSUCCESS2024/4/18 周四44可编辑