《数据结构03排序》PPT课件

,数据结构（DataStructure）,第三章排序（Sorting）,第三章排序,3.1排序的基本概念3.2简单排序方法3.3先进法排序方法3.4基数排序3.5各种排序方法的综合比较,第三章排序,待排序数据元素（记录）的存储结构：typedefintKeyType/定义关键字类型为整型typedefstructKeyTypekey;/关键字项InfoTypeotherinfo;/其他数据项RcdType;/记录类型本章的排序图例只标出了记录的关键字。,3.1排序的基本概念,3.1.1排序的定义3.1.2排序的特性稳定性与不稳定性3.1.3排序的分类3.1.4内排序的特点3.1.5选择排序法,3.1排序的基本概念,3.1.1排序的定义简单定义：排序是按照关键字的非递减或非递增顺序对一组记录重新进行整队（或排列）的操作。数学定义：假设含有n个记录的序列为：r1,r2,rn(3-1)它们的关键字相应为k1,k2,kn,对式(3-1)的记录序列进行排序就是要确定序号1,2,n的一种排列p1,p2,pn使其相应的关键字满足如下的非递增(减)关系：kp1kp2kpn(3-2)也就是使式(3-2)的记录序列重新排列成一个按关键字有序的序列rp1rp2rpn(3-3),3.1排序的基本概念,3.1.2排序的特性稳定性与不稳定性当待排记录中的关键字ki(1,2,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是惟一的。简单地说，稳定性排序-数据排序过后能使值相同的数据，保持原顺序中之相对位置。反之，则称为“不稳定性排序”。若排序的序列中存在两个或两个以上关键字相等的记录时，则排序得到的记录序列的结果不惟一。假设ki=kj(1in,1jn,ij)，且在排序前的序列中ri领先于rj(即i=pivotkey，则减小high否则将Rhigh移至指针low所指位置检测指针所指记录若Rlow.key=pivotkey，则增加low否则将Rlow移至指针high所指位置重复进行，直至low和high指向同一位置。,3.3.1快速排序,17,14,65,28,36,3.3.1快速排序,一趟排序算法：intPartition(RcdTypeR,intlow,inthigh)intpivotkey;R0=Rlow;/将枢轴放在闲置单元pivotkey=Rlow.key;/将枢轴的关键字放在pivotkeywhile(low=pivotkey)high-;/high往左找，比小时停止if(lowhigh)Rlow+=Rhigh;/把比枢轴小的记录移到低端while(lown8不变,3.3.3堆排序,（2）考虑n3,n3n7交换,3.3.3堆排序,（3）考虑n2,n4n2n5n8不变,最大堆,3.3.3堆排序,取出树根与最后一个节点交换,n1n8,n1n7成堆,3.3.3堆排序,n1n7,n1n6成堆,3.3.3堆排序,n1n6,n1n5成堆,3.3.3堆排序,n1n5,n1n4成堆,3.3.3堆排序,n1n4,n1n3成堆,3.3.3堆排序,n1n3,n1n2成堆,3.3.3堆排序,n1n2,voidHeapSort(int*heap,intindex)inti,j,temp;for(i=index/2;i=1;i-)createHeap(heap,i,index);for(i=index-1;i=1;i-)heap1heapi+1;/借助temp交换createHeap(heap,1,i);,voidcreateHeap(int*heap,introot,intindex)inti,j,temp,finish=0;j=2*root;temp=heaproot;while(j=heapj)finish=1;elseheapj/2=heapj;j*=2;heapj/2=temp;,堆排序算法,调用HeapSort(list,index);,3.3.3堆排序,时间复杂度：O(nlog2n)空间复杂度：O(1)优点：最坏情况下时间复杂度也仅为O(nlog2n)。缺点：运行时间主要耗费在建初始堆和调整堆上，排序数据较少时，不值得提倡。,3.4基数排序,基本思想：基数排序：假设记录的逻辑关键字由多个关键字构成，每个关键字可能取r个值，则只要从最低位关键字起，按关键字的不同值将记录“分配”到r个队列之后再“收集”在一起，如此重复趟，最终完成整个记录序列的排序。“基数”指的是r的取值范围。例：关键字为三位整数，其关键字构成是（k2,k1,k0），k2,k1,k0的基数为10例：关键字为5个字母，其关键字构成是（k4,k3,k2,k1,k0），kj,(0收集-分配-收集,基数排序示例,3.4基数排序,记录数组A,计数数组（个位）,（a）初始状态和对“个位数”计数的结果,计数数组累加,记录数组B,30,63,83,74,94,25,05,78,18,09,89,69,（b）计数器的累加结果和记录“复制”后的状态,2,11,6,5,4,10,3,0,1,9,8,7,3.4基数排序,（b）计数器的累加结果和记录“复制”后的状态,计数数组（十位）,计数数组累加,记录数组A,05,09,18,25,30,63,69,74,78,83,89,94,（c）对“十位数”计数、累加和记录“复制”后的状态,记录数组B,6,10,1,2,8,0,3,11,7,9,5,4,3.4基数排序,基数排序需说明的数据结构constintMAX_NUM_OF_KEY=6/关键字项数的最大值constintRADIX=10/关键字的基数constintMAXSIZE=10000typedefstructKeysTypekeysMAX_NUM_OF_KEY;/关键字数组InfoTypeotheritems;/其他数据项/intbitsnum;/关键字的位数RcdType;/基数排序中的记录类型,3.4基数排序,一趟基数排序算法：voidRadixPass(RcdTypeA,RcdTypeB,intn,inti)/对数组A中记录关键字的“第i位”计数，并累计count的值/将数组A中复制到数组B中for(j=0;j=0;k-)/从右端开始复制记录j=Ak.keysi;Bcountj-1=Ak;countj-;/for/RadixPass,3.4基数排序,整个算法：voidRadixSort(SqList/while/RadixSort,TypedefstructRcdType*r;intbitnum;intlength;SqList,3.4基数排序,时间复杂度：最佳状况、最坏状况、平均状况：O(d*n)空间复杂度：最佳状况、最坏状况、平均状况：O(n)优点：平均时间复杂度低；稳定性排序。缺点：空间效率低。,3.5各种排序方法的综合比较,3.5.1时间性能3.5.2空间性能3.5.3排序方法稳定性能3.5.4小结,3.5.1时间性能,按平均的时间性能来分，有三类排序方法：时间复杂度O(nlogn)的方法有：快速排序、堆排序和归并排序，其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在n值较大的情况下，归并排序较堆排序更快。时间复杂度O(n2)的方法有：插入排序、起泡排序和选择排序，其中以插入排序为最常用，特别是已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少。当待排记录序列按关键字顺序有序时，插入排序和起泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变，人们应事先对要排序的记录关键字的分布情况有所了解，才可1对症下药，选择有针对性的排序方法。当待排序记录中其他各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，起泡排序效率最低。,3.5.2空间性能,空间性能指的是排序过程中所需的辅助空间大小。所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为O（1）.快速排序为O(logn),为递归程序执行过程中栈所需的辅助空间。归并排序和基数排序所需辅助空间最多，其空间复杂度为O(n)。,3.5.3排序方法稳定性能,稳定的排序方法指的是对于两个关键字相等的记录在经过排之后，不改变它们在排序之前在序列中的相对位置。除快速排序和堆排序是不稳定的排序方法外，本章讨论的其他排序访方法都是稳定的，例如，例如：对关键字序列（41，3，42，2）进行快速排序，其结果为（2，3，42，41）。“稳定性”是由方法本身决定的，一般来说，排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整时，则排序方法是稳定的。,3.5.4小结,3.5.4小结,若待排序的记录个数n值较小（例如n30），则可选用插入排序法，若记录所含数据项较多，所占存储量大时，应选用选择排序法，反之，若待排序的记录个数n值较大时，应选用快速排序法，若待排序记录关键字有“有序”倾向时，就慎用快速排序，而宁可选用归并排序或堆排序。快速排序和归并排序在n值较小时的性能不及插入排序，可将它们和插入排序“混合”使用，如在快速排序划分子区间的长度小于某值时，转而调用插入排序，或者对待排记录序列先逐段进行插入排序，然后再利用“归并操作”进行两两归并直至整个序列有序为止。基数排序的时间复杂度为O（d*n），因此特别适合于待排记录数n值很大，而关键字“位数d”较小的情况。并且还可以调整基数，减少基数排序的趟数。,3.6谢耳排序法,基本思想：将欲排序的数值依某个间隔长度分成数个数列集合，再针对各个数列集合进行“插入法排序”，重复进行数列分割，每次分割的间割长度缩小为上一次分割间隔长度的二分之一，直到分割间隔为零停止，则数列排序完成。实例：,3.6谢耳排序法,33,57,48,k=2,k=3,k=4,25,k=5,k=6,k=7,92,57,37,k=1,k=2,33,25,k=3,k=4,k=5,k=6,k=7,voidshellsort(Sqlist/while/shellsort,3.6谢耳排序法算法,3.6谢耳排序法,时间复杂度：O(nr)其中1r2空间复杂度：O（1）优点：以插入的方式进行排序，方法简易，由于插入排序法对已排序好的部分会快速处理，故最后几次程序速度会较快。,3.7二叉树排序法,基本思想：将欲排序的元素一一以建立二叉树的方式插入；（1）每一个节点最多只有两个子节点（左节点、右节点）（2）若一节点有子节点，则该节点的数据要比左节点的数据大，且比右节点的数据小（左节点parent右节点）使用二叉树中序遍历的方式将二叉树的节点打输出来，即可得到元素的排序结果。实例：,3.7二叉树排序法,算法：voidbinarytree(int*btree,int*list,intindex)inti,level;btree1=list1;for(i=2;i=index;i+)level=1;while(bt