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

《C程序设计第七章排序.ppt》由会员分享，可在线阅读，更多相关《C程序设计第七章排序.ppt（92页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数 据 结 构 第7章 排序概述概述什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的元素序列调整为“有序”的元素序列。排序的分类待排序元素关键字个数单关键字排序多关键字排序待排序元素的存储介质内部排序：排序过程不需要访问外存便能完成外部排序：排序过程需要访问外存才能完成概述概述内部排序的类别插入类：直接插入排序、折半排序、2-路插入排序、希尔排序分划类：冒泡排序、快速排序选择类：简单选择排序、堆排序归并类：2-路归并排序其他方法：基数排序概述概述排序的两个基本操作比较两个关键字大小将记录从一个位置移动到另一个位置稳定性待排序列 a1,a2,an，其相应的关键字序列 k1,

2、k2,kn，假设ki=kj(1i,jn且i j)，且在排序前的序列中ai领先于 aj。若在排序后的序列中ai仍领先于 aj，则称所用的排序方法是稳定的，反之，则称其是不稳定的。7.1 7.1 插入类排序插入类排序插入类排序将待排序元素逐个插入到已排好序的有序表中，从而得到一个新的有序表。应用插入类排序思想的算法直接插入排序折半插入排序2-路插入排序希尔排序7.1.1 7.1.1 直接插入排序直接插入排序排序过程整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序第i趟直接插入排序的基本思想有序序列A0.i-1Ri无序序列

3、Ai.n-1有序序列A0.i无序序列 Ai+1.n-1直接插入排序例直接插入排序例7.1.1 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&dataj-1tmp;j-)dataj=dataj-1;/元素后移dataj=tmp;/插入到正确位置7.1.17.1.1直

4、接插入排序直接插入排序算法评价时间复杂度正序元素移动次数：0元素比较次数：n-1逆序元素移动次数：元素比较次数：平均情况O(n2)7.1.2 7.1.2 折半插入排序折半插入排序因为 A0.i-1 是一个按关键字有序的有序序列，则可以利用“折半查找”实现“在A0.i-1中查找Ai的插入位置”，如此实现的插入排序为折半插入排序。减少元素关键字间的比较次数，但元素移动次数不变折半插入排序例折半插入排序例折半插入排序算法7.1.2 7.1.2 折半插入排序折半插入排序templatevoidBInsertSort(ElemTypedata,intn)ElemTypetmp;inti,j,mid,lo

5、w,high;for(i=1;in;i+)tmp=datai,low=0,high=i-1;while(low=high)/在datalow.high中查找插入的位置mid=(low+high)/2;/折半if(tmp=low;j-)dataj+1=dataj;/元素后移datalow=tmp;/插入到正确位置7.1.3 2-7.1.3 2-路插入排序路插入排序将插入区域分成大致等长的两段，选择性地插人到其中一段排序过程设置一个和原数组data 同类型，同规模的是数组d，并将其视为循环数组（即位置n-1和0逻辑上相邻）d0=data0，将d0看作为排好序中处于中间位置的元素，从第二个元素dat

6、a1开始做以下操作如果dataid0，将datai插入d0之后的有序序列，并保持插入后有序；反之，将其插入d0之前的有序序列，并保持插入后有序2-2-路插入排序例路插入排序例7.1.3 2-7.1.3 2-路插入排序路插入排序算法评价减少约为n2/8的元素移动次数基准元素选取的好坏直接影响排序的效率7.1.4 7.1.4 希尔排序希尔排序希尔排序又称缩小增量排序将记录序列分成若干子序列，分别对每个子序列进行插入排序。例如：将 n 个记录分成 d 个子序列：R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 其中，d 称为

7、增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为 1。希尔排序例希尔排序例 34288179 22165524996446设增量d=516282479 22345581996446设增量d=31622245528346446997981设增量d=116222428344655647981997.1.4 7.1.4 希尔排序希尔排序希尔排序算法templatevoidShellSort(ElemTypedata,intincrements,intn,intincrementsLength)inti,j,k;ElemTypetmp;for(k=0;kincrementsLength;

8、k+)/进行以incrementsk为增量的排序for(i=incrementsk;i=incrementsk;j-=incrementsk)if(tmp=dataj-incrementsk)break;dataj=dataj-incrementsk;dataj=tmp;7.1.4 7.1.4 希尔排序希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的元素组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序7.1.4 7.1.4 希尔

9、排序希尔排序算法评价算法效率依赖于增量序列的选择时间复杂度在O(n3/2)到O(n7/6)之间增量序列的取法最后一个增量必须为1其他增量间保持“互质”7.2 7.2 分划类排序分划类排序分划类排序通过一趟划分确定一个元素在序列中的位置，保证在它之前的一组元素不比它大，之后的不比它小，接着对两组元素继续分划，直至待排序列有序。应用插入类排序思想的算法冒泡排序快速排序7.2.1 7.2.1 冒泡排序冒泡排序排序过程将第一个和第二个元素的关键字进行比较，若为逆序，则将两元素互换；接着比较第二个和第三个元素的关键字，依次类推，直至最后两个元素的完成比较，这称为第一趟冒泡排序。第一趟排序分划出一组元素个

10、数为n-1的待排序列和一个关键字最大的元素。第i趟对前n-i+1个的元素进行类似的排序操作，得到一组元素个数为n-i的待排序列和一个关键字次大的元素。这样不断分划直至一趟分划时无元素互换为止。7.2.1 7.2.1 冒泡排序冒泡排序假设在排序过程中，元素序列A1.n的状态为：无序序列无序序列A1.n-i+1有序序列有序序列 An-i+2.nn-i+1无序序列无序序列A1.n-i有序序列有序序列 An-i+1.n比较相邻记录，将关键字最大比较相邻记录，将关键字最大的记录的记录交换到交换到 n-i+1 的位置上的位置上第第 i 趟起泡排序趟起泡排序冒泡排序例冒泡排序例7.2.1 7.2.1 冒泡排

11、序冒泡排序冒泡排序算法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 7.2.1 冒泡排序冒泡排序算法评价最好情况（正序）移动次数：0比较次数：n-1最坏情况（逆序）移动次数：3n(n-1)/2比较次数：n(n-1)/2T(n)=O(n2)7.2.2

12、 7.2.2 快速排序快速排序一趟快速排序选第一个待排序元素作为枢轴（或支点pivot），根据枢轴将待排序列划分为两个子列这两个子列必须满足以下条件：一个子列的元素关键字都不大于枢轴的关键字，另一个子列的元素关键字都不小于枢轴的关键字。7.2.2 7.2.2 快速排序快速排序首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无无 序序 的的 元元 素素 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序7.2.2 7.2.2 快速排序快速排序排序过程对待排序列A进行快速排序的递归算

13、法QuickSort(A)可以描述如下：如果A中元素的个数为0或1，则返回；否则，继续选取A中的一个元素p作为枢轴（pivot）将A中剩下的元素“划分”成两个不相交的集合：QuickSort(A1),p,QuickSort(A2)一趟快速排序例一趟快速排序例7.2.2 7.2.2 快速排序快速排序/对datalow.high进行分划，确定枢轴的位置，并返回其所在位置/子序列中，在枢轴之前（后）的元素均不大（小）于它templateintPartition(ElemTypedata,intlow,inthigh)ElemTypepivot=datalow;/用子序列的头元素作为枢轴while(l

14、owhigh)while(low=pivot)high-;datalow=datahigh;/比枢轴小的元素移到低端while(low=datalow)low+;datahigh=datalow;/比枢轴大的元素移到高端datalow=pivot;/确定枢轴的合适位置returnlow;/返回枢轴的位置一趟快速排序算法7.2.2 7.2.2 快速排序快速排序快速排序算法/对databegin.end进行快速排序templatevoidQuickSort(ElemTypedata,intbegin,intend)if(begin=end)/data长度小于等于时返回return;intpivot

15、=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 7.2.2 快速排序快速排序算法分析最好情况每次中间值作为枢轴T(n)=O(nlog2n)最坏情况每次总选最大或最小元素作为枢轴T(n)=O(n)平均情况T(n)=O(nl

16、ogn)三数中值分割法7.3 7.3 选择类排序选择类排序选择类排序逐趟扫描未排序的部分，从中选取一个元素移动到合适的位置。应用选择类排序思想的算法简单选择排序树形选择排序堆排序7.3.1 7.3.1 简单选择排序简单选择排序假设排序过程中，待排记录序列的状态为：有序序列有序序列A1.i-1无序序列无序序列 Ai.n第第 i 趟简单选择排序趟简单选择排序从中选出关键字最小的从中选出关键字最小的元素元素有序序列有序序列A1.i无序序列无序序列 Ai+1.n7.3.1 7.3.1 简单选择排序简单选择排序排序过程第一趟扫描所有待排序元素，找出关键字最小的元素并将它与第一个元素进行交换；第i趟，扫描

17、待排序列中剩余n-i+1个元素，找出关键字最小的元素与序列中第i个位置上的元素交换重复上述操作,直到所有的元素都放到正确的位置上为止简单选择排序例简单选择排序例简单选择排序算法7.3.1 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(datajdatamin)min=j;Swap(datai,datamin);/将datai与第i小的元素交换7.3.1 7.3.1 简单选择排序简

18、单选择排序算法分析最好情况比较次数：移动次数：0最坏情况比较次数：移动次数：3(n-1)T(n)=O(n)7.3.2 7.3.2 树形选择排序树形选择排序简单选择排序中一趟排序中的比较操作可能在前一趟中已经做过，但前一趟中未保存这些比较结果，因此在后一趟的排序中又重复执行了这些操作。为了解决这个问题，树形选择排序应运而生。算法思想先将n个元素的关键字两两比较，然后将其中 个较小者两两比较，如此重复，不断的淘汰较大者，最终选出关键字最小的元素树形选择排序例树形选择排序例7.3.3 7.3.3 堆排序堆排序堆的定义：堆是满足下列性质的数列a1,a2,，an：或或(小顶堆)(大顶堆)12,36,27

19、,65,40,34,98,81,73,55,49 小顶堆12,36,27,65,40,14,98,81,73,55,49 不是堆7.3.3 7.3.3 堆排序堆排序若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子aia2i a2i+1 1236276549817355403498不是堆不是堆147.3.3 7.3.3 堆排序堆排序堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。建大顶堆98,53,55,18,4,22,2424,53,55,18,4,22,98交换 98 和 24重新调整为大顶堆55,53,24,18,4,22,98 22,18,

20、53,98,4,24,55经过筛选7.3.3 7.3.3 堆排序堆排序排序过程将待排序列A0n-1调整为大顶堆；将堆顶元素A0（即关键字最大的元素）与堆尾元素（即堆中最后一个元素）交换，从堆中除去堆尾元素(即关键字最大的元素)，同时调整堆中剩余元素，使它们恢复堆属性；反复进行步骤2，直至堆中元素个数为1。7.3.3 7.3.3 堆排序堆排序堆排序需解决的两个问题：如何将初始的待排序列调整为一个堆？因堆顶元素与堆尾元素交换后，新的堆顶元素可能破坏了堆属性，如何再调整成为堆？第二个问题解决方法输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中较大者进

21、行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例例堆排序调整例堆排序调整例7.3.3 7.3.3 堆排序堆排序第一个问题解决方法从最后一个非叶子结点（即第 个元素）开始对所有非叶子结点调整操作建堆例建堆例 含7个元素的无序序列（22,18,53,98,4,24,55）2218552449822551853244982255985324418985522532441853调整堆算法7.3.37.3.3堆排序堆排序/将datai.n-1中的元素调整为大顶堆templatevoidHeapAdjust(ElemTypedata,inti,intn)ElemT

22、ypetmp;intchild;for(tmp=datai;LeftChild(i)datachild)/取较大的孩子结点child+;if(tmpdatachild)datai=datachild;elsebreak;datai=tmp;7.3.3 7.3.3 堆排序堆排序堆排序算法/堆排序templatevoidHeapSort(ElemTypedata,intn)inti;for(i=n/2;i=0;i-)/建堆HeapAdjust(data,i,n);/将堆的根结点与最后的一个叶结点交换,并进行调整for(i=n-1;i0;i-)Swap(data0,datai);HeapAdjust

23、(data,0,i);7.3.3 7.3.3 堆排序堆排序算法评价最好情况：O(n)最坏情况：O(nlogn)平均：O(nlogn)7.4 7.4 归并类排序归并类排序归并将两个有序列合并成为一个新的有序列2-路归并排序将相邻的元素两两归并，得到 个长度为2或1的有序子序列，再将这些子序列两两归并，如此重复，直至得到一个长度为n的有序列为止2-路归并排序例“归并归并”算法算法/将数组data中，lptr.rptr-1rptr.rightEnd两部分的元素进行合并/tmpArr为合并时的辅存空间templatevoidMerge(ElemTypedata,ElemTypetmpArr,intlp

24、tr,intrptr,intrightEnd)intleftEnd=rptr-1;intptr,i;ptr=i=lptr;while(lptr=leftEnd&rptr=rightEnd)if(datalptr=datarptr)tmpArrptr+=datalptr+;elsetmpArrptr+=datarptr+;while(lptr=leftEnd)tmpArrptr+=datalptr+;while(rptr=rightEnd)tmpArrptr+=datarptr+;for(;i=rightEnd;i+)datai=tmpArri;2-2-路归并排序算法路归并排序算法templat

25、evoidMPass(ElemTypedata,ElemTypetmpArr,intn,intmergeLength)inti=0;while(i=n-2*mergeLength)Merge(data,tmpArr,i,i+mergeLength,i+2*mergeLength-1);i=i+2*mergeLength;if(i+mergeLengthn)Merge(data,tmpArr,i,i+mergeLength,n-1);/2-路归并算法非递归实现templatevoidMergeSortNonRecursion(ElemTypedata,intn)intmergeLength=1;

26、/mergeLength记录每趟归并的步长ElemType*pArr=NULL;pArr=newElemTypen;/pArr为合并时的辅存空间while(mergeLengthn)MPass(data,pArr,n,mergeLength);mergeLength*=2;deletepArr;7.4 7.4 归并类排序归并类排序算法评价T(n)=O(nlogn)缺点空间复杂度为O(n)算法中需要较多的拷贝工作7.5 7.5 基数排序基数排序无须比较关键字通过“分组”和“收集”两个过程来完成排序任务借助“多关键字排序”的思想7.5.1 7.5.1 多关键字的排序多关键字的排序假设待排序列 a1

27、,a2,an中每个元素ai有d个关键字，该序列对关键字 有序是指：对序列中任意两个元素ai和aj(1 i j n)都满足下列有序关系：当两个元素的所有关键字都相等时，则必须保持其稳定性。其中 称为最主位关键字，称为最次位关键字。7.5.1 7.5.1 多关键字的排序多关键字的排序排序方法最高位优先法（MSD）先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值接着让每个子序列对次关键字k2排序，又分成若干更小的子序列依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列最低位优先法（LSD）从最低位关键字kd起进行排序，然后再对高一

28、位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列7.5.1 7.5.1 多关键字的排序多关键字的排序MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序7.5.2 7.5.2 基数排序基数排序基数排序依次根据各关键字分量进行“分配”、“收集”完成排序在单关键字排序中，一个关键字可以看作由若干个关键字分量复合而成，如整数可视为若干数位的集合。基数排序例基数排序例7.5.2 7.5.2 基数排序基数排序用数组实现的基数

29、排序算法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 7.5.2 基数排序基数排

30、序用数组实现基数排序的缺点虽然不需要进行“比较”操作，但仍需要大量的元素移动操作还需要额外的空间来存放10个队列链式基数排序用链表作存储结构的基数排序7.5.2 7.5.2 基数排序基数排序链式基数排设置10个队列，fronti和reari分别为第i个队列的头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变元素的指针值，将链表中的元素分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列链式基数排

31、序（第一趟）例链式基数排序（第一趟）例静态链表静态链表classSLListstructNodeintkeyDIGITS;intinfo;intnext;friendostream&operator(ostream&os,SLList&s);public:SLList():data(NULL),length(0);SLList();voidArrange();/重排voidInit(intarr,intn);voidRadixSort();/链式基数排序private:voidDistribute(int,int,int);/分配voidCollection(int,int,int);/收集N

32、ode*data;intlength;7.5.2 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 7.5.2 基

33、数排序基数排序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 7.5.2 基数排序基数排序/用SLList实现的基数排序voi

34、dSLList:RadixSort()inti;intfrontRADIX,rearRADIX;/从最低位优先依次对各关键字进行分配收集for(i=0;iDIGITS;i+)Distribute(front,rear,i);Collection(front,rear,i);7.5.2 7.5.2 基数排序基数排序重排链式基数排序产生的是一个有序循环链表，只能对它进行顺序访问，无法进行随机访问，因此有时需要对元素重新排列，将元素按照链表结点中next域的值调整位置使其顺序存储具体做法顺序扫描有序链表，将链表中第i个结点移动至静态链表中的第i个分量重排例重排例重排算法7.5.2 7.5.2 基数排

35、序基数排序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 7.5.2

36、 基数排序基数排序算法分析空间复杂度O(r+n)时间复杂度T(n)=O(d(n+r)其中，n为待排序元素个数，d为元素的关键字分量数，r为基数7.6 7.6 内部排序的比较内部排序的比较排序方法平均情况最好情况最坏情况基数排序O(d(n+r)O(d(n+r)O(d(n+r)2-路归并排序O(n log n)O(n log n)O(n log n)堆排序O(n log n)O(n)O(n log n)快速排序O(n log n)O(n log n)O(n2)希尔排序O(n)直接插入排序O(n2)O(n)O(n2)简单选择排序O(n2)O(n2)O(n2)7.6 7.6 内部排序的比较内部排序的比

37、较从平均性能而言，快速排序最佳，但最坏情况下不如堆排序和归并排序直接插入排序、简单选择排序、冒泡排序是O(n2)的排序，不适合处理n较大的情况从空间复杂度角度考虑归并排序需要与待排序列等量的辅助存储空间，其空间复杂度为O(n)；基数排序次之，空间复杂度为O(r+n)；快速排序最坏情况下需要的栈空间为O(n)，最好情况下需要的栈空间为O(logn)；其余排序算法的空间复杂度为O(1)7.6 7.6 内部排序的比较内部排序的比较从稳定性角度考虑直接插入排序、冒泡排序和基数排序都是稳定的堆排序、快速排序、希尔排序和简单选择排序是不稳定的7.6 7.6 内部排序的比较内部排序的比较选择排序方法时应综合

38、考虑这些因素待排序的元素数目n关键字的结构及其初始状态对稳定性的要求语言工具的条件存储结构时间和辅助空间复杂度等7.67.6内部排序的比较内部排序的比较排序的一般下界任何只借助“比较”的排序算法在最坏情况下都需要 次比较7.7 7.7 外部排序外部排序外部排序是指大文件的排序，用于处理输入数据量较大、无法同时全部载入内存的排序情况7.7.17.7.1外部存储设备外部存储设备根据外存设备的存储介质分类磁盘文件直接存取设备磁带文件顺序存取设备7.7.17.7.1外部存储设备外部存储设备磁盘存储器由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等部分组成磁盘上标明一个具体位置需要

39、用一个三维地址：柱面号、盘面号、块号磁盘读写一块数据的时间需要由3部分组成：寻道时间、等待时间和传输时间磁带存储器一种以磁带为存储介质、能存储大量数字信息的装置通常由磁带控制器和磁带驱动器（或称磁带机）组成在磁带上读写一块数据需要的时间由两部分组成：延迟时间和传输时间7.7.2 7.7.2 外部排序的方法外部排序的方法外部排序以下两个阶段组成根据可用内存大小，将n个待排序元素的文件分成若干个子文件，依次读入内存并利用内部排序算法对它们进行排序，然后将排序后得到的子文件写入外存，这些有序的子文件或排过序的元素组称为归并段或顺串将这些归并段逐趟归并，归并段逐渐由小到大，直至得到整个有序文件为止归并

40、7.7.2 7.7.2 外部排序的方法外部排序的方法外部排序需要的总时间=内部排序所需的时间(mtIS)+外存信息读写的时间(dtIO)+内部归并所需的时间(sutmg)其中，m为初始归并段个数，tIS是得到一个初始归并段所耗费的内部排序时间的均值；d为总的外存读/写次数，tIO为一次读/写时间的均值；s为归并的趟数，utmg是对u个元素进行内部归并所需的时间 若增加k或减少归并段个数m便能减少s，从而减小外存读写次数d，但单纯增加k将使utmg增加 7.7.3 7.7.3 败者树败者树败者树是指在锦标赛（选择树）中，每个父结点存放其孩子结点中的“败者”，而让“胜者”参加更高一层的比赛，而在根

41、结点之上再增加一个结点，存放整个比赛的获胜者败者树例败者树例7.7.3 7.7.3 败者树败者树置换-选择排序采用败者树来生成初始归并段最佳归并树对长度不等的m个初始归并段构造一颗哈夫曼树作为归并树，则可以保证在外部归并时所需要的外存读写次数达到最小，这棵归并树被称为最佳归并树7.8 7.8 学习要点学习要点熟练掌握各内部排序算法的基本思想、具体过程以及实现算法；掌握各种排序算法时间复杂度、空间复杂度的分析方法和稳定性的含义排序算法大致可分为5类：插入类排序、分划类排序、选择类排序、归并类排序和基数排序。通过对各种典型的排序算法的学习，能够在实际问题上选择或设计适合的排序算法。Thank You!