数据结构教学笔记第十章排序

52,49,80,36,14,61,23,97,14,23,36,49,52,61,75,80,假设含n个记录的序列为{R1,R2,⋯，Rn{K1,K2,⋯，Kn{Rp1,Rp2,⋯，Rpn若整个排序过程不需 在本章讨论内部排序的各种方法，然后介绍外部排序的基本过程R[1..i-1R[1..i]。R[0]=R[i];//设置“哨兵”for(j=i-1;R[0].key<R[j].key;--returnj+1;R[i]for(j=i-1;R[0].key<R[j].key;--j);R[j+1]=R[j]3．i2，3，⋯n,voidInsertionSort(ElemR[],intn)for(i=2;i<=n;++i){R[0]=R[i];//为监视forj=i-1;R[0].keyR[j].key;jR[j+1]=R[j];//记录后移R[j+1]R[0];}}//最好的情况（关键字在记录序列中顺序有序的情况（关键字在记录序列中逆序有序R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。voidBiInsertionSort(ElemR[]，intn)for(i=2;i<=L.length;++i){R[0]R[i];R[i]R[0]low=1;high=i-1;while(low<=high)R[low..high]中折半查找插入的位置m=(low+high)/2;//折半if(R[0].key<R[m].key))highm-1;elselowm+1}forj=i-1;j>=high+1;jR[j+1]=R[j];//记录后移R[high+1]=R[0];//插入}}//voidLInsertionSort(ElemSL[]，int{SL[0].key=MAXINT;SL[0].next=1;SL[1].next=0;for(i=2;i<=n;++i)for(j=0,k=SL[0].next;SL[k].key<=SL[i].key;j=k,k=SL[k].next){SL[j].next=i;SL[i].next=k;}//iivoidArrange(ElemSL[],intn)pSL[0].next;pfor(i=1;i<n;++i)SL[1..i-1]while(p<i)p=SL[p].next;qSL[p].next;qif(p!=i)SL[p]←→SL[i];iSL[i].nextp;}pq;p}}//四、排序（又称缩小增量排序ndd{R[1]，R[1+d]，R[1+2d]，⋯，R[1+kd]{R[2]，R[2+d]，R[2+2d]，⋯，R[2+kd]⋯{R[d]，R[2d]，R[3d]，⋯，R[kd]，R[(k+1)d]为1。第二趟排序，设增量d=第三趟排序，设增量d=voidSInsert(ElemR[],intdk)for(i=dk+1;i<=n;++iifR[i].key<R[i-dk].key)R[iR[0]R[i];for(j=i-dk;j>0&&(R[0].key<R[j].key);j-=dk)R[j+dk]R[j];R[j+dk]=R[0];}}//SvoidSSort(ElemR[],intdlta[],intt)for(k=0;k<t;SInsert(R,dlta[k]);//一趟增量为dlta[k]的插入排}//S操作，将无序序列中关键字最大的记录“交换”到R[n-i+1]的位置上。voidBubbleSort(ElemR[],int{ii=while(i{lastExchangeIndex=1;for(j=1;j<i;j++)if(A[j+1]<A[j]){lastExchangeIndex=}i=}//}//n-0小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)(i+1≤j≤t)52,49,80,36,14,58,61,97,23,调整为:23,49,14,36,(52)58,61,97,80,别为:s和t,之后逐渐减小high，增加low，R[high].key≥52，而intPartition(ElemR[],intlow,inthigh)（后）的记录均不大（小）pivotkey=while(low<high)while(low<high&&--while(low<high&&}returnlow;}//intPartition(ElemR[],intlow,inthigh)（后）的记录均不大（小）R[0]=pivotkeyR[low].key;while(low<high)while(low<high&&--R[low]=while(low<high&&R[high]=}R[low]R[0];returnlow;}//voidQSort(ElemR[],intlow,inthigh)if(low<high-1){//长度大于1pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,}}//voidQuickSort(ElemR[],intn)QSort(R,1,}//T(n)=Tpass(n)+T(k-1)+T(n-随机分布的，则k取1至n中任意一值的可能性相同，由此可得快速排序所需时间的Tavg(1)≤bR(t).key和 R[i..n]n-i+1简 排序的算法描述如下vodSelectSort(EemR[],itn) 序列[..n]作简单选择排序。for(i=1;i<n;++i){//ij=SelectMinKey(R,//R[i..n]keyif(i!=j)//i}}//Se对n个记录进行简单选择排序， 移动记录的次数，最值为 利用在第一趟选中已经得到的关键字比较的结果。 质的数列{r1,r2,或 树：其左、右子树分别是堆，并且当/右子树不空时，根结点的值小于(或大于)左/右子树根结由此，若上述列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或 即是 的特性对记录序列进行排序的一种排序方法。具体作法是n-1个记录交换，如此反复直排序结束。使整二叉树为堆。堆排序的 下所示voidHapSort(ElemR[],intn)//R1..n]进行堆排for(i=n/2;i>0;--iR[1..n]建成大顶堆HeapAdjust(R,i,n);for(i=n;i>1;--i){//将堆顶记录和当 HeapAdjust(R,1,i-1);//R[1..i-1]}}//其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“选 vodHeapAdjust(ElemR[]ints,itm)//R[..m]中记录的关字除R[s].eR[s]R[s..m]成为一个大顶堆（//记录的关键字而言rc=for(j=2*s;j<=m;j*=2)//keyif(j<m&&R[j].key<R[j+1].key)jkeyif(rc.key>=R[j].key)rcsR[s]=R[j];s=}R[]=rc;//}/对k2(k-对n个关键字，建成深度为 次数至多为4n; 整“堆 n-1次总共进行的关键字比较的次数不超O(nlo 。在内部排序中，通常用的是2路归并排序即：将两个置相邻的有子序归并为一个归并”法 如下vodM ElemSR[],ElemTR[],inti,intm,intn)for(j=m+1,k=i;i<=m&&j<=n;++k)if(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=//将剩余的SR[i..m]到TRif(j<=n)TR[k..n]}//如果记录无序序列R[s..t]的两部分voidMsort(ElemSR[],ElemTR1[],ints,intt)if(s==t)TR1[s]=SR[s];elsem=Msort(SR,TR2,s,m);Msort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);}}//voidMergeSort(ElemR[])MSort(R,R,1,n);}//并的时间复杂度为O(n)，总共需进行logn趟。{R,R2,每个记录R中含有d个键字(K0,K1,⋯,Kd-1),则称上述记录序列对关键字(K0 i⋯,Kd-有序是指对于序中任意两个记录Ri和Rj(1≤i<≤n)i (K0,K,⋯,Kd-1)<(K0,K 实现关键字排序通常有两种作法:最优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子最低位先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完为止。排 记录 (“前一个”关键字不同的)子序列关键字。LSD的排序过程如下:对K2对K1对K0键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排法。例如：对下列这组键字{209,386,768,185,247,606,230,834,53901,⋯，9100的顺序将它们“收集”在一起;然后按其“十位数”取值分别为,1,⋯，9数”重复遍上操作，便可得到这组关键字的有序序列。计算上实现基数排序时为减少所需辅助空间应采用链表作结构，待 录以针相链，构成一个链表 将记分配到不同的“链队列” 的“关字位”相同；f[9]→369→23→139←r[9]第一次收集到p→230→367→167→27→138→368→239→1f[3]→230→237→138→2f[p→230→237→1第三次分f[1]→138→139→1 O(n);收集为rd)(d为“基”),d为“分-0.7一、 插入为最好，特别是对些对键字近似有序的记录序列尤为如此；时间复杂度为O(n)的排序方法只有，基数排序。O(n) 复杂;而对于快速排序而言，这是最不好的情况，此时的时性能蜕化为O(n2)， 况指是排序过 所需的辅助空间大小度为O(1)；快速排序为 )，为栈所需的辅助空间归并排序所需辅助空间最多，其空间复杂度为O(nO(d)。当对多关键字的录序列进行LSD 快速排序和堆行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂为logn)。(基数排序不是基于“比较关键字”的排序方,所以它不受这个限制) 描这类于比较关键字”进行排序的排序方法。描述排序的判定树有两个特点 树上的叶子结点包含所有可能情况则由上图所示“判定树的深度 4”可以推出“至多进行三次比较”即可完成三次比较”才能完成对三个关键的排序。较，所得判定树的度都是3。当关键字的个数超过3之后，不同的排序方法其判定树的深度不同。例如，对4个关键字进行排序时，直接插入的判定树的深度为6,而折半入的判定树的深度为5。4!=2424个叶子结点，其深度的最小值为6。nn!n!叶子结二叉树的深度不小于则对n个关键字进行排序的。利用 近所以基“较关字进行排序的排序方法，可能达到的最快的时间复杂度为O(nlogn 10.8读/写外存中一个“数据块”的数据需要的时间为：TI/O=tseek+ 其中tsee为寻查时间(查找该数块所在磁道tla为等(延迟)时 twm为传输数据块中n个记录的时常称外存中这记录有序子序列为“归并段”;例如：假设有一个含0,000个记录的磁盘文件，而前用的算一次只能对2路归并(即两两归并)105个归并段第二趟由5个归并段得到 归并段第三趟由3个归并段