数据结构第7章.ppt

《数据结构第7章.ppt》由会员分享，可在线阅读，更多相关《数据结构第7章.ppt（135页珍藏版）》请在三一办公上搜索。

1、JYP,1,第7章 排序,数据元素之间的次序是一种重要的关系。本章学习最典型的排序算法，特别讨论内、外排序的不同策略。还介绍排序结果的顺序化方法。,JYP,2,7.1 引言,在数据结构中，数据元素之间的次序是一种重要的关系。排序的应用：查询结果需要按用户指定的属性排序。在已排序的数组中查找记录可最多用O(log2n)时间。核对两个已按学号排序的学生记录表可用O(m+n)时间完成。,JYP,3,记录 表示数据元素，具有一个或多个数据字段。关键字 用于区分记录的字段。表 记录的有限集合。给定一个记录表（R0,R1,Rn-1），设记录Ri的关键字值为Ki。关键字上存在一种次序关系 和一种相等关系=，

2、使得对于任意两个关键字值x和y，x=y，或x y，或y x。关系 满足传递性。用xy表示x=y或x y。,JYP,4,排序 确定一种置换p，使得记录表（Rp(0),Rp(1),Rp(n-1)）的关键字满足性质Kp(0)Kp(1)Kp(n-1)。简单而言，排序就是按关键字非递减次序排列记录。如果在输入记录表中Ki=Kj（i j），且在排序后Ri在Rj之前，则称相应的排序方法是稳定的。否则就是不稳定的。根据整个排序过程能否在内存中完成，可将排序方法分为内排序和外排序。,JYP,5,记录的类定义：template class Element public:KeyType getKey()const

3、return key;/取记录的关键字值 void setKey(KeyType k)key=k;/修改记录的关键字/其它操作private:KeyType key;/关键字/其它字段;假设在KeyType被实例化时，相应实参类型的、=和=等已定义。,JYP,6,7.2 插入排序,插入排序的基本步骤：将记录R插入一个已排好序的记录序列R0,R1,Ri（K0K1Ki）中，使得新的有i+2个记录的序列也是排好序的。函数Insert实现了此步骤：template void insert(const Element e,Element*list,int i)/将e插入已排好序的 list0,listi

4、中，/使结果序列也排好序。list至少可容纳i+2个记录。while(i=0),JYP,7,插入排序从序列R0开始，连续插入记录R1,R2,Rn-1。n个记录可以通过n1次插入排序，如函数InsertionSort所示：template void InsertionSort(Element*list,const int n)for(int j=1;j n;j+)insert(listj,list,j 1);,JYP,8,分析：在最坏情况下，insert(e,list,i)在插入前要作i+1次比较。InsertionSort对i=j1=0,1,n2调用insert，其最坏情况时间复杂性是O()=

5、O(n2)插入排序的实际时间与输入表的相对无序状态有关。记录Ri是左出序的当且仅当Ki。,JYP,9,插入步骤中的循环只对左出序记录迭代。设k是左出序记录个数，则插入排序的时间是O(k+1)n)。当k=0，插入排序的时间为O(n)。这说明，当输入表中左出序记录很少时，插入排序的实际性能十分理想。,JYP,10,例7.1 设n=5，输入关键字为5,4,3,2,1，则每次插入后表中记录的排列如下：,这时插入排序的性能达到最坏情况。,JYP,11,例7.2 设n=5，输入关键字为2,3,4,5,1，则每次插入后表中记录的排列如下：,这时只有R4是左出序的。对于j=1,2,3，每次插入的时间只需O(1

6、)；而对于j=4，插入时间为O(n)。,JYP,12,插入排序是稳定的。由于算法简单，对于较小的n（例如n20），插入排序几乎是最快的。插入排序的改进：1 二分插入排序 2 链表插入排序,JYP,13,7.3 希尔排序,希尔排序又称为减少增量排序。以插入排序为基础，并利用插入排序在最好情况下的性能，改善整个排序的性能。观察输入序列 8,7,6,5,1,2,3,4，其中左出序记录有7个。在插入排序中，首次交换8和7，只能减少1个左出序记录。如果首次交换8和1，则可减少2个左出序记录。,JYP,14,根据以上观察，可以跨越式地交换记录：将整个记录表划分为若干个子表，其相邻记录相隔incr个位置，i

7、ncr称为增量。利用插入排序对每个子表排序，以快速减少整个表中的左出序记录。每完成一次上述过程，增量减少，继续利用插入排序对按新增量划分的每个子表排序。最后一次增量必须为1，这等同于普通的插入排序，但由于前面的预处理，整个记录表已基本有序，此次插入排序有望快速完成。,JYP,15,例7.3 设n=8，输入序列为8,7,6,5,1,2,3,4，取incr=4,2,1。处理过程如下所示：,JYP,16,增量的一个较有效的选择是从 incr=n/3+1开始，按incr=incr/3+1减少增量。由于跨越式交换，希尔排序是不稳定的。为了反映增量，对InsertionSort及其调用的insert作少量

8、修改，得到用于希尔排序的InsertionSort2以及insert2。,JYP,17,template void insert2(const Element e,Element*list,int i,int incr)while(i=0),JYP,18,进一步可得希尔排序函数ShellSort：template void ShellSort(Element*list,int n)int incr=n;do/对每个增量 incr=incr/3+1;for(int start=0;start 1);,JYP,19,大规模实验研究表明：当记录个数n很大时，希尔排序对记录的移动次数在n1.25到1.

9、6n1.25的范围之内。这比插入排序有实质性的改进。,JYP,20,7.4 快速排序,插入排序将控制当前插入的基准记录Ri插入相对于已排好序的子表(R0,Ri1)的正确位置，而快速排序将基准记录Ri放在相对于整个记录表的正确位置。设输入表为(Rleft,Rright)，如果Ri放在位置s(i)，则有KjKs(i)（j s(i)）。,JYP,21,因此，根据Ri的关键字大小，整个记录表被划分为左子表(Rleft,Rs(i)1)和右子表(Rs(i)+1,Rright)，如下图所示：,由于左、右子表的记录分别在位置s(i)的左、右边，可独立地对这两个子表排序。,JYP,22,基准记录可任意选取，在此

10、选第一个记录Rleft。划分记录表：从左到右扫描，找到关键字大于等于Kleft的记录Ri；从右到左扫描，找到关键字小于等于Kleft的记录Rj；交换Ri和Rj；继续上述过程，直到i，j错位。,JYP,23,算法QuickSort给出了实现细节：template void QuickSort(Element*list,const int left,const int right)/排序listleft,listright，任选listleft为基准记/录，假设listleft.keylistright+1.key。if(left pivot);if(i j)InterChange(list,i,

11、j);while(i j);,JYP,24,InterChange(list,left,j);QuickSort(list,left,j 1);/排序左子表 QuickSort(list,j+1,right);/排序右子表 其中函数InterChange(list,a,b)交换记录lista和listb。调用QuickSort(list,0,n 1)可对表list的第0到第n 1个记录排序。为了简化边界判断，假设记录listn的关键字不小于其余关键字。,JYP,25,例7.4 设输入表记录的关键字为(26,5,37,1,61,11,59,15,48,19)，每次调用QuickSort时记录表的

12、状态如下：,JYP,26,分析：用于划分记录表的时间是O(n)，设下面的c都是常数。（1）用Tworst(n)表示快速排序的最坏时间复杂性。在最坏情况下，两个子表的长度分别为n1和0，因此 Tworst(n)cn+Tworst(n1)cn+c(n1)+Tworst(n2)c=cn(n+1)/2=O(n2),JYP,27,（2）用Topt(n)表示快速排序的最佳时间复杂性。在最佳情况下，两个子表的长度相同，每个子表的长度最多是n/2，因此 Topt(n)cn+2Topt(n/2)cn+2(cn/2+2Topt(n/4)2cn+4Topt(n/4)cn log2n+nTopt(1)=O(n log

13、 n),JYP,28,（3）根据下面的引理7.1，快速排序的平均时间复杂性也是O(n log n)。而且，实验结果表明，快速排序的平均性能最好。引理7.1：设Tavg(n)为快速排序的平均时间复杂性，则存在常数k，使得对于n2，Tavg(n)knlogen 成立。证明：在调用QuickSort(list,0,n 1)中，K0被放在位置j。两个子表的长度为j和n1j，相应的平均时间是Tavg(j)+Tavg(n1j)。由于j可按同等概率取值0到n1，因此,JYP,29,Tavg(n)cn+=cn+，n2(7.1)设Tavg(0)b和Tavg(1)b，b为常数，k=2(b+c)。对n应用归纳法可证

14、，Tavg(n)knlogen（n 2）。,JYP,30,当n=2，由(7.1)式可得：Tavg(2)2c+2b 2kloge2。假设对于2n m，Tavg(n)knlogen。则 Tavg(m)cm+=cm+cm+(7.2),JYP,31,由于jlogej是j的递增函数，由(7.2)式可得 Tavg(m)cm+=cm+=cm+=kmlogem+(cm+),JYP,32,当m2，cm+0，所以 Tavg(m)kmlogem,JYP,33,对基本快速排序算法的改进：基准记录的选择：选当前记录表的第一、中间和最后一个记录中关键字为中间值的记录。用排序小记录表较快的方法如插入排序代替快速排序。当需要

15、排序的记录表小于一定长度时，快速排序已使整个表接近于排好序，这时对整个记录表调用一次插入排序可使所有记录就序。,JYP,34,快速排序的最大递归深度是n。递归排序两个子表中较小的，再用循环代替第二个递归，可使递归深度最多是O(log n)，如函数ImpQuickSort所示：template void ImpQuickSort(Element*list,const int left,const int right)/排序listleft,listright，任选listleft为/基准记录，设listleft.key listright+1.key while(left pivot);if(i

16、 j)InterChange(list,i,j);while(i j);,JYP,35,InterChange(list,left,j);if(right j=j left)/左子表较小 ImpQuickSort(list,left,j 1);left=j+1;else/右子表较小 ImpQuickSort(list,j+1,right);right=j 1;,JYP,36,设S(n)为ImpQuickSort所需的栈空间，每层递归调用需要栈空间为c，则 S(n)c+S(n/2)2c+S(n/4)clog2n+S(1)=O(log n)。不难看出，快速排序是不稳定排序。,JYP,37,7.5

17、归并排序,7.5.1 迭代归并排序 归并排序的基础是归并，即将两个已排序的表归并为一个已排序的表。在迭代归并排序中，需要归并的两个表：(initListl,initListm)(initListm+1,initListn)生成的结果表是(mergedListl,mergedListn)。,JYP,38,函数merge：template void merge(Element*initList,Element*mergedList,const int l,const int m,const int n)for(int i1=l,iResult=l,i2=m+1;i1=m,JYP,39,if(i1

18、m)for(int t=i2;t=n;t+)mergedListiResult+t-i2=initListt;else for(int t=i1;t=m;t+)mergedListiResult+t-i1=initListt;对merge的分析：for循环最多迭代nl+1次。循环之外的if语句总共最多移动nl+1个记录。因此，总时间是O(nl+1)。所需的辅助空间是O(nl+1)。,JYP,40,迭代归并排序的基本思想：将有n个记录的输入表解释为n个已排序表，每个表的长度为1。成对归并这些表，得到n/2个已排序表，每个表的长度为2（如果n是奇数，则最后一个表的长度为1）。再归并这n/2个表，如

19、此继续直到只剩下一个已排序的表。,JYP,41,例7.5 对输入表(26,5,77,61,11,59,15,48,19)，的每一遍扫描中归并子表的过程：,JYP,42,可见，需要对输入表进行多次归并扫描。设扫描时输入表中已排序子表的长度为len（最后一个子表的长度可能小于len），则经过一次归并扫描后已排序子表的长度变为2len，如下所示：,JYP,43,用i作为扫描指针，指向需归并的两个子表的前一个的第一记录，并随着归并的完成向右移动。如果in2len，则至少还有两个长度都是len的子表需要归并，否则需要作特殊边界处理。,JYP,44,函数MergePass：template void Me

20、rgePass(Element*initList,Element*resultList,const int n,const int len)/一遍归并扫描。将表initList的相邻子表归并到表resultList for(int i=0;i=n 2len;i+=2len)merge(initList,resultList,i,i+len1,i+2len1);/剩下的记录数 2len if(i+len1 n1)/归并最后两个长短不一的子表 merge(initList,resultList,i,i+len1,n1);else for(int t=i;t=n1;t+)resultListt=in

21、itListt;/复制最后一个子表,JYP,45,函数MergeSort反复调用MergePass完成排序：template void MergeSort(Element*list,const int n)Element*tempList=new Element n;for(int l=1;l n;l*=2)/l是当前被归并子表的长度 MergePass(list,tempList,n,l);l*=2;MergePass(tempList,list,n,l);/最后一遍可能只是复制 delete tempList;,JYP,46,对MergeSort的分析：对输入表进行多次扫描。第1遍归并长度

22、为1的表，第2遍归并长度为2的表。第i遍扫描归并长度为2i-1的表。总共需要log2n次扫描。每遍扫描的时间为O(n)。归并排序的总时间为O(n log n)。不难看出，归并排序是稳定排序。,JYP,47,7.5.2 递归归并排序,递归归并排序的基本思想：将记录表划分成大致等长的左、右子表。递归排序这些子表。再归并已排序的子表，从而使整个记录表就序。,JYP,48,例7.6 对输入表(26,5,77,61,11,59,15,48,19)进行递归归并排序过程中的子表划分：,JYP,49,将子表从一个数组归并到另一个数组需要复制数据。采用链表表示可避免数据复制。假设每个元素至少有两个字段：link

23、和key，其结构定义如下：template class Element private:KeyType key;/关键字 int link;/其它字段public:Element()link=-1;/-1表示空指针;,JYP,50,假设：所有访问Element私有数据成员的的函数已声明为Element的友元。listi.key和listi.link分别是记录i的key和link字段的值（0in1）。初始时listi.link=1（0in1），即每个记录构成一个只含其本身的链表。,JYP,51,函数ListMerge(list,start1,start2)将两个由start1和start2指向的

24、按关键字非递减次序链接的链表归并为一个按关键字非递减次序链接的链表，并返回首记录指针：template int ListMerge(Element*list,const int start1,const int start2)/将分别由start1和start2指向的已排序链表归并为/一个已排序链表，并返回其首记录的下标。记录/之间通过整型下标链接。int iResult,iStart,i1,i2;if(liststart1.key=liststart2.key)/定位结果表的首记录 iStart=iResult=start1;i1=liststart1.link;i2=start2;,JYP

25、,52,else iStart=iResult=start2;i2=liststart2.link;i1=start1;while(i1-1,JYP,53,函数rMergeSort利用ListMerge实现递归归并排序，并返回已排好序链表的首记录指针：template int rMergeSort(Element*list,const int left,const int right)/将listleft,listright按key排序。返回已/排序链表的首记录下标。if(left=right)return left;/最多只含一个记录 int mid=(left+right)/2;/分别排序

26、左、右半部分，并归并所得的两个已排序链表 return ListMerge(list,rMergeSort(list,left,mid),rMergeSort(list,mid+1,right);当需要对list0,listn1排序时，可调用rMergeSort(list,0,n1)。此排序也是稳定的。,JYP,54,7.6 堆排序,堆排序只需要O(1)的辅助空间，同时其最坏和平均时间复杂性也都是O(n log n)。堆排序通过最大堆的插入和删除操作实现排序：首先将n个记录插入一个初始为空的堆，接着逐个从堆中取出记录。然而，还可以通过函数adjust更快地构建具有n个记录的堆。给定一棵二叉树T

27、，其左、右子树都满足最大堆的性质，但其根结点却不一定满足，函数adjust调整T使得整个二叉树都满足最大堆性质。,JYP,55,template void adjust(Element*tree,const int root,const int n)/结点下标不大于n Element e=treeroot;int k=e.getKey();for(int j=2*root;j=treej.getKey()break;/如果k不小于左、右子女/中的较大者，则e可放在j的双亲处 treej/2=treej;/将第j个记录上移 treej/2=e;设以root为根的树深为d，其计算时间为O(d)。,

28、JYP,56,算法HeapSort首先利用函数adjust构建最大堆，如下图所示：,JYP,57,接着对记录表list作n 1遍处理，每次将当前最大堆的第一个记录与最后一个交换，并将当前最大堆记录数减少1，重新调整。由于第一个记录的关键字总是堆中最大的，经过交换该记录一定是就序的。调用HeapSort(list,n)即可对list1,listn排序。,JYP,58,template void HeapSort(Element*list,const int n)/按关/键字非递减次序排序list1,listn for(int i=n/2;i=1;i-)/将list转化为最大堆 adjust(li

29、st,i,n);for(i=n 1;i=1;i-)/排序list Element t=listi+1;listi+1=list1;list1=t;/交换list1和listi+1 adjust(list,1,i);/重建堆,JYP,59,例7.7 用HeapSort对(26,5,77,1,61,11,59,15,48,19)的排序过程：,JYP,60,JYP,61,JYP,62,JYP,63,JYP,64,分析：设2k1n 2k，则与记录表对应的完全二叉树有k层，第i层的结点数2i1。第一个for循环对每个有子女的结点调用adjust一次。该循环的时间不大于各层结点数与该层结点可移动的最大距离

30、的积之和，即 第二个for循环调用adjust共n1次，最大深度为 log2(n+1)。因此，堆排序的总计算时间是O(n log n)。而且，只需要O(1)辅助空间。,JYP,65,7.7 基数排序,当n个记录的关键字listi.key（0in）的取值是0到n1范围内的整数时，可以用下列代码对其排序：for(int i=0;i n;i+)resultlisti.key=listi;这里用关键字值来确定记录在最终就序数组中的位置。这就是最基本的箱排序。其中，我们为n个关键字值安排n个箱子，并根据关键字值将记录分配到对应的箱中。此方法效率极高，无论记录关键字的初始顺序如何，只需要O(n)时间即可完

31、成排序。,JYP,66,在实际应用中，一个箱子可以存放多个记录，同时关键字的取值范围不必与n直接关联。为了有效地利用箱排序的思想，可以将关键字解释为多个子关键字：K0,Kd1（K0是最高位，Kd1是最低位）。如果记录表R0,Rn-1中的任意两个记录Ri和Rj（0i j n）都满足 则称该记录表相对于关键字(K0,Kd1)已排好序。,JYP,67,例如，排序100张关键字值为0到99的卡片可看成对两个子关键字K0和K1的排序，其中K0对应十位，K1对应个位。我们按最低位优先（简称LSD）策略应用箱排序解决此问题：首先根据K1将卡片逐张分配到0号箱到9号箱中。接着，将8号箱的卡片放在9号箱的之前，

32、将0号箱的卡片放在1号箱的之前。再根据K0按照稳定排序的要求将卡片逐张分配到0号箱到9号箱中，按照从0到9的箱号顺序收集即得到已排序的卡片。,JYP,68,可见，如果关键字是十进制数，可将其中的每个十进制位看成一个子关键字，并按LSD策略用10个箱子对每个子关键字进行箱排序。一般地，在基数排序中，用基数r分解关键字。当r=10，则得到上述十进制分解。如果关键字是长度为d的小写英文标识符，则可分解为d个子关键字(K0,Kd1)，其中，Ki a,b,z（0i d），r=26。基数r排序需要r个箱子。,JYP,69,假设记录表是R0,Rn-1。关键字用基数r分解，每个分解为d位，每位的取值是0到r

33、1，则需要r个箱子。记录元素的类定义如下：class Element public:private:int keyd;/关键字数组，d是常数/其它字段 int link;,JYP,70,每个箱子中的记录链接成队列，fi和ei（0i r）分别指向第i个箱子的首、尾记录。函数RadixSort给出了用LSD策略实现基数r排序的细节：int RadixSort(Element*list,const int d,const int n)/按关键字key0,keyd-1排序(list0,listn-1)，/0keyi radix，radix是常数 int fradix,eradix;/radix个队列的

34、首、尾指针 for(int i=0;i n1;i+)listi.link=i+1;listn1.link=-1;int current=0;/链接成一个以current开/头的链表，用-1表示空指针,JYP,71,for(i=d 1;i=0;i-)/对keyi排序 for(int j=0;j-1;current=listcurrent.link)/分配记录 int k=listcurrent.keyi;if(fk=-1)fk=current;else listek.link=current;ek=current;for(j=0;fj=-1;j+);/找到第一个非空队列 current=fj;i

35、nt last=ej;for(int k=j+1;k-1)listlast.link=fk;last=ek;listlast.link=-1;/for(i=d-1;i=0;i-)结束 return f0;/返回已就序链表的第一个记录下标,JYP,72,分析：RadixSort对数据作d遍扫描，每遍扫描用O(n+r)时间，总计算时间是O(d(n+r)。例7.8 设需要排序的10个数的取值范围是0,999。数的每一位作为一个子关键字，d=3，r=10。排序过程如后面两页所示。,JYP,73,JYP,74,JYP,75,JYP,76,7.8 基于链表和映射表排序结果的顺序化,对于基于链表的排序结果，

36、有时需要按次序就地重新排列，使它们在物理上也是顺序的。设记录表R0,Rn-1经排序后的结果是一个按关键字非递减次序链接的链表，且first是链表的首记录指针。将记录R0和Rfirst交换。如果first 0，则表中应有一个记录Rx，其link字段值为0。如果能够修改Rx的link字段，使其指向原位于R0的记录的新位置first，则剩余记录R1,Rn-1也是按关键字非递减次序链接的。,JYP,77,但在单链表中，我们无法快速确定结点R0的前驱Rx。于是可将R0的link字段设置为first，表示原位于R0的记录已移到Rfirst。这样，R0还作为R1,Rn-1链表中的虚拟结点。借助此虚拟结点，我

37、们可找到剩余记录链表的首结点。重复上述过程n1次即可完成重新排列。一般地，设记录表R0,Ri-1已在物理上按序排列，Rfirst是剩余记录Ri,Rn-1链表的首记录，记录Ri和Rfirst交换后，将新Ri记录的link字段设置为first，表示原位于Ri的记录已移到Rfirst。,JYP,78,同时，注意到作为剩余记录Ri,Rn-1链表的首记录下标的first总是大于或等于i，我们可以经过虚拟结点，找到剩余记录链表的首记录下标。函数list实现了上述方法：template void list(Element*list,const int n,int first)/重新排序由first指向的链表

38、中的记录，使list0,listn-1/中的关键字按非递减次序排列 for(int i=0;i n 1;i+)/找到应放到位置i的记录。由于位置0,1,i-1的记录已/就位，该记录下标一定i while(first i)first=listfirst.link;/经过虚拟结点,JYP,79,int q=listfirst.link;/listq 是按非递减次序的下一个/记录，可能是虚拟记录 if(first!=i)/交换listi 和listfirst，并将listi.link/设置为原listi的新位置 Element t=listi;listi=listfirst;listfirst=t;

39、listi.link=first;first=q;,JYP,80,例7.9 对(26,5,77,1,61,11,59,15,48,19)进行链表排序后，所得链表如下所示：,JYP,81,list的for循环每次迭代后记录表的状态如下，变化用粗体字表示，虚拟结点的link字段用带下划线的字体表示：,JYP,82,JYP,83,JYP,84,JYP,85,JYP,86,对list的分析：设有n个记录，for循环迭代n1次。每次最多交换2个记录，需要3次记录移动。如果每个记录的长度为m，则每次交换的代价是3m。所以，最坏情况下记录移动的总代价是O(mn)。在while循环中，任何结点最多被检查一次，

40、所以while循环的总时间是O(n)。显然，list所需的辅助空间是O(1)。,JYP,87,链表排序不适用于希尔排序、快速排序和堆排序，因为记录表的顺序表示是这些方法的基础。对于这些方法可以采用映射表t，表的每一个单元对应一个记录。映射表单元起着对记录间接寻址的作用。排序开始时，ti=i，0in1。如果要求交换Ri和Rj，则只需交换表单元ti和tj。排序结束时，关键字最小的记录是Rt0，最大的记录是Rtn-1，所要求的记录排列是Rt0,Rt1,Rtn-1，如下一页所示。,JYP,88,JYP,89,有时为了避免间接寻址，还需要根据映射表t确定的置换在物理上重新排列记录。整个置换由不相交的环路

41、组成。含记录i的环路由i,ti,t2i,tki构成，且tki=i。例如，上一页的置换由两个环路组成，第一个包含记录R0和R4，第二个包含记录R1，R3和R2。函数table首先沿着包含R0的环路将记录移到其正确位置。接着，如果包含R1的环路未被移动过，则沿着该环路将记录移到其正确位置。由此继续移动包含R2,R3,Rn-2的环路，最终得到物理上就序的记录表。,JYP,90,template void table(Element*list,const int n,int*t)/重新排列list0,listn-1，使其对应序列listt0,/listtn-1,n1 for(int i=0;i p=l

42、isti;int j=i;do int k=tj;listj=listk;tj=j;j=k;while(tj!=i);listj=p;/p中的记录应该移到位置j tj=j;,JYP,91,例7.10 一个根据映射表t对记录顺序化的例子：,JYP,92,对table的分析：设每个记录占用m个存储单元，则所需辅助空间为O(m)个存储单元。for循环执行了n1次。如果对于某些i的取值，ti i，则存在一个包含k 1个不同记录Ri,Rti,Rtk-1i的环路。重新排列这些记录需要k+1次移动。设kj是在for循环中i=j时以Rj开头的非平凡环路的记录个数。对于平凡环路，则令kj=0。记录移动的总次数是

43、,JYP,93,当=n且存在n/2个非平凡环路时，记录移动的总次数达到最大值 3n/2。移动一个记录的代价是O(m)，总的计算时间是O(m n)。,JYP,94,7.9 外排序,7.9.1 概述 需要排序的记录表大到计算机内存不能容纳时，内排序已不足以解决问题。假设需要排序的记录表存放在磁盘上。由于计算机访问内存的速度比访问磁盘的速度快得多，影响外排序性能的主要是访问磁盘的次数。磁盘的读、写以IO块为单位。一个IO块通常可包含多个记录。,JYP,95,影响磁盘读写时间的有以下三个因素：寻找时间：将读写头定位于正确的柱面所用时间。等待时间：本磁道中所需块旋转到读写头下所用时间。传输时间：将块中数

44、据读入内存或写到磁盘所用时间。其中，就数据传输而言，寻找和等待都是辅助性的，但其时间却较长。为了提高传输效率，IO块的容量一般都较大，通常可包含数千字节。,JYP,96,外排序的最基本方法是归并，包括两个阶段：（1）根据内存容量将输入记录表分为若干段，并利用某种内排序方法逐个对这些段排序。这些已排序的段又称为归并段（runs）。（2）归并第一阶段生成的归并段，直到最终只剩一个归并段。由于归并算法只要求同一时刻两个归并段的前端记录在内存，因此经过归并，可以生成比内存大的归并段。,JYP,97,例7.11 设记录表有4500个记录，可用于排序的计算机内存容量是750个记录，IO块长度是250个记录

45、。按上述方法，排序步骤如下：,JYP,98,JYP,99,分析用符号：tseek=最长寻找时间tlatency=最长等待时间trw=读写一个IO块（250个记录）所需时间tIO=tseek+tlatency+trwtIS=内排序750个记录所需时间ntm=将n个记录从输入缓冲区归并到输出缓冲区所 需时间,JYP,100,例7.11中排序4500个记录的操作时间：,JYP,101,由于tIO tIS，tIO tm，影响计算时间的主要因素是输入输出操作的次数，而后者又主要依赖于对数据扫描的遍数。例7.11中，生成初始归并段需要1遍数据扫描，归并需要 遍数据扫描。一遍扫描需要输入输出218个IO块，

46、总的输入输出时间是(+1)218tIO=132tIO。归并时间是 4500tm=12000tm。,JYP,102,显然，k路归并（k 2）可以减少数据扫描遍数。例如，如果在上例中采用6-路归并，则只需对数据扫描一遍即可完成排序。此外，初始归并段应尽可能长，从而减少初始归并段个数。在内存容量给定的情况下，可以利用动态流动的思想，生成平均长度几乎是通常方法所得的两倍的归并段。但这些归并段长短不一，对它们归并的次序也会影响计算时间。下面将分别讨论这些问题。,JYP,103,7.9.2 k路归并,按2-路归并，给定m个归并段，相应的归并树有log2m+1层，需要对数据扫描log2m遍。采用k路归并可减

47、少数据扫描遍数。如下图对16个归并段进行4-路归并只需扫描数据2遍：,JYP,104,一般地，采用k路归并需要对数据扫描logkm遍。因此，当k 2时，采用k路归并可有效减少输入输出时间。但k路归并要求从k个归并段的前端记录中选择关键字最小的输出。可以采用具有k个叶结点的败者树来选择关键字最小的记录。从败者树中每选一个最小记录并重新调整需要O(log2k)时间，所以对n个记录归并一遍需要的时间是O(n log2k)。归并logkm遍的CPU处理时间是O(n log2k logkm)=O(n log2m)，即与k无关。,JYP,105,还应该看到，当k超过一定范围时，输入输出时间并不随着k的增大

48、而减少。因为：k路归并所需的缓冲区个数随着k的增大而增加；在内存容量给定情况下，缓冲区容量随着k的增大而减小；这又导致IO块的有效容量减小，从而使一遍数据扫描需要更多的IO块操作。因此，当k超过一定值时，输入输出时间反而会随着k的增大而增加。k值的最佳选择与磁盘参数和可用于缓冲区的内存容量有关。,JYP,106,7.9.3 生成初始归并段,用传统的内排序方法生成初始归并段，需要将内存容纳的所有记录都排序好后再全部输出到磁盘。从在排序过程中没有内外存数据交换的意义上看，这属于静态方法，由此生成的归并段最多与内存容纳的记录数同样大。如果采用动态流动的方法，即在生成归并段的过程中不断将记录写到磁盘，

49、同时从磁盘读入新的记录到内存，则可能生成比内存容量大的归并段。,JYP,107,设内存可容纳k个记录，用r0,r1,rk1表示，记录的输入和输出通过IO缓冲实现。输入k个记录后，这些记录都属于当前归并段。从属于当前归并段的内存记录中选关键字最小的记录rq（0q k）输出到当前归并段。从输入表读入下一个记录到rq，如果此记录的关键字不小于当前归并段的最后一个记录的关键字，则该记录也属于当前归并段，否则属于下一个将生成的归并段。,JYP,108,将内存记录所属的归并段号作为第一子关键字，记录原来的关键字作为第二子关键字，下一个要输出的记录是k个记录中关键字最小的。败者树是组织这些记录的有效结构：每

50、个非叶结点i有一个字段li（1ik），表示在结点i比赛的败者。rni表示ri所属的归并段号（0ik）。l0和q都存放整个比赛的胜者记录下标。rc存放当前归并段号。rq存放rq所属的归并段号。,JYP,109,rmax存放将生成的实际归并段总数。LastKey存放当前最后一个输出记录的关键字值。当输入记录表已读空时，我们可以构造归并段号为rmax+1的虚拟记录，以将败者树中的实际记录“顶”出。,JYP,110,函数runs实现了上述采用败者树动态流动生成初始归并段的方法：1 template 2 void runs(const int k)3 Element*r=new Elementk;4 i