C程序设计第七章排序.ppt

数据结构第7章排序,概述,什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的元素序列调整为“有序”的元素序列。排序的分类待排序元素关键字个数单关键字排序多关键字排序待排序元素的存储介质内部排序：排序过程不需要访问外存便能完成外部排序：排序过程需要访问外存才能完成,概述,内部排序的类别插入类：直接插入排序、折半排序、2-路插入排序、希尔排序分划类：冒泡排序、快速排序选择类：简单选择排序、堆排序归并类：2-路归并排序其他方法：基数排序,概述,排序的两个基本操作比较两个关键字大小将记录从一个位置移动到另一个位置稳定性待排序列a1,a2,an，其相应的关键字序列k1,k2,kn，假设ki=kj(1i,jn且ij)，且在排序前的序列中ai领先于aj。若在排序后的序列中ai仍领先于aj，则称所用的排序方法是稳定的，反之，则称其是不稳定的。,7.1插入类排序,插入类排序将待排序元素逐个插入到已排好序的有序表中，从而得到一个新的有序表。应用插入类排序思想的算法直接插入排序折半插入排序2-路插入排序希尔排序,7.1.1直接插入排序,排序过程整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序第i趟直接插入排序的基本思想,直接插入排序例,7.1.1直接插入排序,直接插入排序算法,/直接插入排序,数组data用于存放待排序元素，n为待排序元素个数templatevoidInsertSort(ElemTypedata,intn)ElemTypetmp;inti,j;for(i=1;idatai-1)continue;tmp=datai;/保存待插入的元素datai=datai-1;for(j=i-1;j0/插入到正确位置,7.1.1直接插入排序,算法评价时间复杂度正序元素移动次数：0元素比较次数：n-1逆序元素移动次数：元素比较次数：平均情况O(n2),7.1.2折半插入排序,因为A0.i-1是一个按关键字有序的有序序列，则可以利用“折半查找”实现“在A0.i-1中查找Ai的插入位置”，如此实现的插入排序为折半插入排序。减少元素关键字间的比较次数，但元素移动次数不变,折半插入排序例,折半插入排序算法,7.1.2折半插入排序,templatevoidBInsertSort(ElemTypedata,intn)ElemTypetmp;inti,j,mid,low,high;for(i=1;i=low;j-)dataj+1=dataj;/元素后移datalow=tmp;/插入到正确位置,7.1.32-路插入排序,将插入区域分成大致等长的两段，选择性地插人到其中一段排序过程设置一个和原数组data同类型，同规模的是数组d，并将其视为循环数组（即位置n-1和0逻辑上相邻）d0=data0，将d0看作为排好序中处于中间位置的元素，从第二个元素data1开始做以下操作如果dataid0，将datai插入d0之后的有序序列，并保持插入后有序；反之，将其插入d0之前的有序序列，并保持插入后有序,2-路插入排序例,7.1.32-路插入排序,算法评价减少约为n2/8的元素移动次数基准元素选取的好坏直接影响排序的效率,7.1.4希尔排序,希尔排序又称缩小增量排序将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将n个记录分成d个子序列：R1，R1+d，R1+2d，R1+kdR2，R2+d，R2+2d，R2+kdRd，R2d，R3d，Rkd，R(k+1)d其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。,希尔排序例,设增量d=5,设增量d=3,设增量d=1,7.1.4希尔排序,希尔排序算法,templatevoidShellSort(ElemTypedata,intincrements,intn,intincrementsLength)inti,j,k;ElemTypetmp;for(k=0;k=incrementsk;j-=incrementsk)if(tmp=dataj-incrementsk)break;dataj=dataj-incrementsk;dataj=tmp;,7.1.4希尔排序,特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的元素组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序,7.1.4希尔排序,算法评价算法效率依赖于增量序列的选择时间复杂度在O(n3/2)到O(n7/6)之间增量序列的取法最后一个增量必须为1其他增量间保持“互质”,7.2分划类排序,分划类排序通过一趟划分确定一个元素在序列中的位置，保证在它之前的一组元素不比它大，之后的不比它小，接着对两组元素继续分划，直至待排序列有序。应用插入类排序思想的算法冒泡排序快速排序,7.2.1冒泡排序,排序过程将第一个和第二个元素的关键字进行比较，若为逆序，则将两元素互换；接着比较第二个和第三个元素的关键字，依次类推，直至最后两个元素的完成比较，这称为第一趟冒泡排序。第一趟排序分划出一组元素个数为n-1的待排序列和一个关键字最大的元素。第i趟对前n-i+1个的元素进行类似的排序操作，得到一组元素个数为n-i的待排序列和一个关键字次大的元素。这样不断分划直至一趟分划时无元素互换为止。,7.2.1冒泡排序,假设在排序过程中，元素序列A1.n的状态为：,无序序列A1.n-i+1,有序序列An-i+2.n,n-i+1,无序序列A1.n-i,有序序列An-i+1.n,比较相邻记录，将关键字最大的记录交换到n-i+1的位置上,第i趟起泡排序,冒泡排序例,7.2.1冒泡排序,冒泡排序算法,templatevoidBubbleSort(ElemTypedata,intn)intlastSwapIndex=n-1;/用于记录最后一次交换的元素下标inti,j;for(i=lastSwapIndex;i0;i=lastSwapIndex)lastSwapIndex=0;for(j=0;jdataj+1)Swap(dataj,dataj+1);lastSwapIndex=j;,7.2.1冒泡排序,算法评价最好情况（正序）移动次数：0比较次数：n-1最坏情况（逆序）移动次数：3n(n-1)/2比较次数：n(n-1)/2T(n)=O(n2),7.2.2快速排序,一趟快速排序选第一个待排序元素作为枢轴（或支点pivot），根据枢轴将待排序列划分为两个子列这两个子列必须满足以下条件：一个子列的元素关键字都不大于枢轴的关键字，另一个子列的元素关键字都不小于枢轴的关键字。,7.2.2快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,无序的元素序列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行快速排序,7.2.2快速排序,排序过程对待排序列A进行快速排序的递归算法QuickSort(A)可以描述如下：如果A中元素的个数为0或1，则返回；否则，继续选取A中的一个元素p作为枢轴（pivot）将A中剩下的元素“划分”成两个不相交的集合：QuickSort(A1),p,QuickSort(A2),一趟快速排序例,7.2.2快速排序,/对datalow.high进行分划，确定枢轴的位置，并返回其所在位置/子序列中，在枢轴之前（后）的元素均不大（小）于它templateintPartition(ElemTypedata,intlow,inthigh)ElemTypepivot=datalow;/用子序列的头元素作为枢轴while(low=pivot)high-;datalow=datahigh;/比枢轴小的元素移到低端while(low=datalow)low+;datahigh=datalow;/比枢轴大的元素移到高端datalow=pivot;/确定枢轴的合适位置returnlow;/返回枢轴的位置,一趟快速排序算法,7.2.2快速排序,快速排序算法,/对databegin.end进行快速排序templatevoidQuickSort(ElemTypedata,intbegin,intend)if(begin=end)/data长度小于等于时返回return;intpivot=Partition(data,begin,end);/对databegin.end进行分划QuickSort(data,begin,pivot-1);/对低端子列进行递归排序QuickSort(data,pivot+1,end);/对高端子列进行递归排序/快速排序templatevoidQuickSort(ElemTypedata,intn)if(n2)return;QuickSort(data,0,n-1);,7.2.2快速排序,算法分析最好情况每次中间值作为枢轴T(n)=O(nlog2n)最坏情况每次总选最大或最小元素作为枢轴T(n)=O(n)平均情况T(n)=O(nlogn)三数中值分割法,7.3选择类排序,选择类排序逐趟扫描未排序的部分，从中选取一个元素移动到合适的位置。应用选择类排序思想的算法简单选择排序树形选择排序堆排序,7.3.1简单选择排序,假设排序过程中，待排记录序列的状态为：,有序序列A1.i-1,无序序列Ai.n,第i趟简单选择排序,从中选出关键字最小的元素,有序序列A1.i,无序序列Ai+1.n,7.3.1简单选择排序,排序过程第一趟扫描所有待排序元素，找出关键字最小的元素并将它与第一个元素进行交换；第i趟，扫描待排序列中剩余n-i+1个元素，找出关键字最小的元素与序列中第i个位置上的元素交换重复上述操作,直到所有的元素都放到正确的位置上为止,简单选择排序例,简单选择排序算法,7.3.1简单选择排序,templatevoidSelectionSort(ElemTypedata,intn)inti,j,min;for(i=0;in;i+)min=i;for(j=i+1;jn;j+)/选择datai+1.n-1中最小的元素if(dataj0;i-)Swap(data0,datai);HeapAdjust(data,0,i);,7.3.3堆排序,算法评价最好情况：O(n)最坏情况：O(nlogn)平均：O(nlogn),7.4归并类排序,归并将两个有序列合并成为一个新的有序列2-路归并排序将相邻的元素两两归并，得到个长度为2或1的有序子序列，再将这些子序列两两归并，如此重复，直至得到一个长度为n的有序列为止,2-路归并排序例,“归并”算法,/将数组data中，lptr.rptr-1rptr.rightEnd两部分的元素进行合并/tmpArr为合并时的辅存空间templatevoidMerge(ElemTypedata,ElemTypetmpArr,intlptr,intrptr,intrightEnd)intleftEnd=rptr-1;intptr,i;ptr=i=lptr;while(lptr=leftEnd,2-路归并排序算法,templatevoidMPass(ElemTypedata,ElemTypetmpArr,intn,intmergeLength)inti=0;while(ivoidMergeSortNonRecursion(ElemTypedata,intn)intmergeLength=1;/mergeLength记录每趟归并的步长ElemType*pArr=NULL;pArr=newElemTypen;/pArr为合并时的辅存空间while(mergeLengthn)MPass(data,pArr,n,mergeLength);mergeLength*=2;deletepArr;,7.4归并类排序,算法评价T(n)=O(nlogn)缺点空间复杂度为O(n)算法中需要较多的拷贝工作,7.5基数排序,无须比较关键字通过“分组”和“收集”两个过程来完成排序任务借助“多关键字排序”的思想,7.5.1多关键字的排序,假设待排序列a1,a2,an中每个元素ai有d个关键字，该序列对关键字有序是指：对序列中任意两个元素ai和aj(1ijn)都满足下列有序关系：当两个元素的所有关键字都相等时，则必须保持其稳定性。其中称为最主位关键字，称为最次位关键字。,7.5.1多关键字的排序,排序方法最高位优先法（MSD）先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值接着让每个子序列对次关键字k2排序，又分成若干更小的子序列依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列最低位优先法（LSD）从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列,7.5.1多关键字的排序,MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序,7.5.2基数排序,基数排序依次根据各关键字分量进行“分配”、“收集”完成排序在单关键字排序中，一个关键字可以看作由若干个关键字分量复合而成，如整数可视为若干数位的集合。,基数排序例,7.5.2基数排序,用数组实现的基数排序算法,voidRadixSort(intdata,intn)constintradix=10;constintdigits=10;inti,j,k,factor;queuequeuesradix;for(i=0,factor=1;idigits;i+,factor*=radix)for(j=0;jn;j+)queues(dataj/factor)%radix.push(dataj);/分配for(k=j=0;jradix;j+,k+)/收集while(!queuesj.empty()datak=queuesj.front();queuesj.pop();,7.5.2基数排序,用数组实现基数排序的缺点虽然不需要进行“比较”操作，但仍需要大量的元素移动操作还需要额外的空间来存放10个队列链式基数排序用链表作存储结构的基数排序,7.5.2基数排序,链式基数排设置10个队列，fronti和reari分别为第i个队列的头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变元素的指针值，将链表中的元素分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列,链式基数排序（第一趟）例,静态链表,classSLListstructNodeintkeyDIGITS;intinfo;intnext;friendostream,7.5.2基数排序,voidSLList:Distribute(intfront,intrear,intdigit)inti,index;for(i=0;i0;i=L.datai.next)index=datai.key/(int)pow(10.0,digit)-datai.key/(int)pow(10.0,digit+1)*10;if(frontindex=0)frontindex=i;elsedatarearindex.next=i;rearindex=i;,链式基数排序“分配”算法,链式基数排序“收集”算法,7.5.2基数排序,voidSLList:Collection(intfront,intrear,intdigit)inti,current;for(i=0;fronti=0;i+);/找到第一个非空子表data0.next=fronti;/头结点指向第一个非空子表中第一个结点current=reari+;for(;iRADIX;i+)if(fronti=0)continue;datacurrent.next=fronti;/链接两个非空子表current=reari;datacurrent.next=0;,链式基数排序算法,7.5.2基数排序,/用SLList实现的基数排序voidSLList:RadixSort()inti;intfrontRADIX,rearRADIX;/从最低位优先依次对各关键字进行分配收集for(i=0;iDIGITS;i+)Distribute(front,rear,i);Collection(front,rear,i);,7.5.2基数排序,重排链式基数排序产生的是一个有序循环链表，只能对它进行顺序访问，无法进行随机访问，因此有时需要对元素重新排列，将元素按照链表结点中next域的值调整位置使其顺序存储具体做法顺序扫描有序链表，将链表中第i个结点移动至静态链表中的第i个分量,重排例,重排算法,7.5.2基数排序,voidSLList:Arrange()inti,tmp;intcurrent=data0.next;/current存放第一个元素的当前位置for(i=1;ilength;i+)while(currenti)/找到第i个元素，并用current存放其在静态/链表中当前位置current=datacurrent.next;tmp=datacurrent.next;if(current!=i)Swap(datacurrent,datai);/第i个元素调整到位datai.next=current;/指向被移走的元素current=tmp;/为找第i+1个元素做准备,7.5.2基数排序,算法分析空间复杂度O(r+n)时间复杂度T(n)=O(d(n+r)其中，n为待排序元素个数，d为元素的关键字分量数，r为基数,7.6内部排序的比较,7.6内部排序的比较,从平均性能而言，快速排序最佳，但最坏情况下不如堆排序和归并排序直接插入排序、简单选择排序、冒泡排序是O(n2)的排序，不适合处理n较大的情况从空间复杂度角度考虑归并排序需要与待排序列等量的辅助存储空间，其空间复杂度为O(n)；基数排序次之，空间复杂度为O(r+n)；快速排序最坏情况下需要的栈空间为O(n)，最好情况下需要的栈空间为O(logn)；其余排序算法的空间复杂度为O(1),7.6内部排序的比较,从稳定性角度考虑直接插入排序、冒泡排序和基数排序都是稳定的堆排序、快速排序、希尔排序和简单选择排序是不稳定的,7.6内部排序的比较,选择排序方法时应综合考虑这些因素待排序的元素数目n关键字的结构及其初始状态对稳定性的要求语言工具的条件存储结构时间和辅助空间复杂度等,7.6内部排序的比较,排序的一般下界任何只借助“比较”的排序算法在最坏情况下都需要次比较,7.7外部排序,外部排序是指大文件的排序，用于处理输入数据量较大、无法同时全部载入内存的排序情况,7.7.1外部存储设备,根据外存设备的存储介质分类磁盘文件直接存取设备磁带文件顺序存取设备,7.7.1外部存储设备,磁盘存储器由盘片、磁头、盘片主轴、控