数据结构C++PPT7

数据结构第7章内排序肖正信息与智能系统系[e-mail]27.1排序术语及记号术语记录——结点文件——线性表关键码：能够唯一确定结点的一个或若干域。排序码：作为排序运算依据的一个或若干域。组合排序码，(主关键码，次关键码)例，(总分数，数据结构分数，计算引论分数)排序：排序就是将一组杂乱无章的数据按一定的规律排列起来DataStructure3术语排序问题：给定一组记录r1,r2,...rn,其排序码分别为k1,k2,…，kn，将这些记录排成顺序为rs1,rs2,…，rsn的一个序列S，满足条件ks1≤ks2≤ksn。排序算法的稳定性：如果在对象序列中有两个对象r[i]和r[j]，它们的关键码k[i]==k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。内排序——在内存中进行的排序外排序——排序过程还要访问外存(因为待排记录的数量太大，内存容纳不下)DataStructure4基本操作按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序DataStructure57.2三种代价为O(n2)的排序方法7.2.1插入排序DataStructure6教材上插入排序算法templateclassElem,classCompvoidinssort(ElemA[],intn){for(inti=1;in;i++)for(intj=i;(j0)&&(Comp::lt(A[j],A[j-1]));j--)swap(A,j,j-1);}DataStructure7改进的插入排序算法templateclassElem,classCompvoidinssort(ElemA[],intn){for(inti=1;in;i++){Elemx=A[i];j=i-1;while(j0&&(Comp::lt(x,A[j]))){A[j+1]=A[j];j--;}A[j+1]=x;}}DataStructure8加入监视哨的插入排序算法templateclassElem,classCompvoidinssort(ElemA[],intn){for(inti=2;i=n;i++){A[0]=A[i];j=i-1;while(Comp::lt(x,A[j])){A[j+1]=A[j];j--;}A[j+1]=A[0];}}DataStructure9插入排序算法分析最小比较次数：最多比较次数：最少移动次数：最多移动次数：插入排序是一种稳定排序2)1(11maxnniCni1minnC)1(2minnM2)4)(1()1(211maxnninMniDataStructure107.2.2起泡排序DataStructure11教材上起泡排序算法templateclassElem,classCompvoidbubsort(ElemA[],intn){for(inti=0;in-1;i++)for(intj=n-1;ji;j--)if(Comp::lt(A[j],A[j-1]))swap(A,j,j-1);}DataStructure12改进的起泡排序算法templateclassElem,classCompvoidbubsort(ElemA[],intn){intflag;for(inti=0;in-1;i++){flag=FALSE:for(intj=n-1;ji;j--)if(Comp::lt(A[j],A[j-1])){swap(A,j,j-1);flag=TRUE;}if(flag==FALSE)return;}}DataStructure13起泡排序算法分析最小比较次数：最多比较次数：最少移动次数：最多移动次数：稳定算法1minnC2)1(11maxnniCni0minM2)1(3311maxnniMniDataStructure147.2.3直接选择排序DataStructure15直接选择排序算法templateclassElem,classCompvoidselsort(ElemA[],intn){for(inti=0;in-1;i++){intlowindex=i;//Rememberitsindexfor(intj=n-1;ji;j--)//Findleastif(Comp::lt(A[j],A[lowindex]))lowindex=j;//Putitinplaceswap(A,i,lowindex);}}DataStructure16直接选择排序算法分析比较次数：最少移动次数：最多移动次数：稳定算法2)1()1(1120maxminnniinCCnini0minM)1(3maxnM一个交换包含三次移动DataStructure17交换指针，减少交换记录的开销DataStructure18时间代价(n)(n2)(n2)WorstCase(n)(n2)(n2)AverageCase(n)00BestCaseSwaps(n2)(n2)(n2)WorstCase(n2)(n2)(n2)AverageCase(n2)(n2)(n)BestCaseComparisons:SelectionBubbleInsertionDataStructure197.3Shell排序缩小增量排序法法(不稳定算法，时间代价Ｏ(n1.5)原理：n很小时，或基本有序时排序速度较快DataStructure20Shell排序算法//ModifiedversionofInsertionSorttemplateclassElem,classCompvoidinssort2(ElemA[],intn,intincr){for(inti=incr;in;i+=incr)for(intj=i;(j=incr)&&(Comp::lt(A[j],A[j-incr]));j-=incr)swap(A,j,j-incr);}templateclassElem,classCompvoidshellsort(ElemA[],intn){//Shellsortfor(inti=n/2;i2;i/=2)//Foreachincrfor(intj=0;ji;j++)//Sortsublistsinssort2Elem,Comp(&A[j],n-j,i);inssort2Elem,Comp(A,n,1);}DataStructure217.4快速排序DataStructure22快速排序DataStructure23快速排序算法templateclassElem,classCompvoidqsort(ElemA[],inti,intj){if(j=i)return;//Listtoosmallintpivotindex=findpivot(A,i,j);swap(A,pivotindex,j);//Putpivotatend//kwillbefirstpositiononrightsideintk=partitionElem,Comp(A,i-1,j,A[j]);swap(A,k,j);//PutpivotinplaceqsortElem,Comp(A,i,k-1);qsortElem,Comp(A,k+1,j);}templateclassElemintfindpivot(ElemA[],inti,intj){return(i+j)/2;}DataStructure24快速排序算法templateclassElem,classCompintpartition(ElemA[],intl,intr,Elem&pivot){do{//Movetheboundsinuntiltheymeetwhile(Comp::lt(A[++l],pivot));while((r!=0)&&Comp::gt(A[--r],pivot));swap(A,l,r);//Swapout-of-placevalues}while(lr);//Stopwhentheycrossswap(A,l,r);//Reverselastswapreturnl;//Returnfirstposonright}DataStructure25轴值选在最左DataStructure26快速排序算法分析移动次数与比较次数相比，较少，可以主要考虑比较次数。当初始是有序序列时，最多比较次数：最少比较次数：不稳定算法优化策略：消除递归；仔细选择轴值，小序列用直接插入2)1()(11maxnninCni)log()1(log)8/(83)4/(42)2/(2)(nnOnCnnnCnnCnnCnnCDataStructure277.5归并算法Listmergesort(Listinlist){if(inlist.length()=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),mergesort(l2));}DataStructure28归并排序算法templateclassElem,classCompvoidmergesort(ElemA[],Elemtemp[],intleft,intright){intmid=(left+right)/2;if(left==right)return;mergesortElem,Comp(A,temp,left,mid);mergesortElem,Comp(A,temp,mid+1,right);for(inti=left;i=right;i++)//Copytemp[i]=A[i];inti1=left;inti2=mid+1;for(intcurr=left;curr=right;curr++){if(i1==mid+1)//LeftexhaustedA[curr]=temp[i2++];elseif(i2right)//RightexhaustedA[curr]=temp[i1++];elseif(Comp::lt(temp[i1],temp[i2]))A[curr]=temp[i1++];elseA[curr]=temp[i2++];}}DataStructure29优化归并排序算法templateclassElem,classCompvoidmergesort(ElemA[],Elemtemp[],intleft,intright){if((right-left)=THRESHOLD){inssortElem,Comp(&A[left],right-left+1);return;}inti,j,k,mid=(left+right)/2;if(left==right)return;mergesortElem,Comp(A,temp,left,mid);mergesortElem,Comp(A,temp,mid+1,right);for(i=mid;i=left;i--)temp[i]=A[i];for(j=1;j=right-mid;j++)temp[right-j+1]=A[j+mid];for(i=left,j=right,k=left;k=right;k++)if(temp[i]temp[j