算法分析与设计第四章2(分治法归并分类).ppt
第四章第四章 分治法分治法2008-09-01版权所有：杨波，武汉科技大学理学院 4.4 4.4 归并分类归并分类n分类问题排序q对一个给定含有n个元素（又称为关键字）的集合，按一定次序进行分类（如非降次序）称称n元排序元排序。q常见的排序方法：n冒泡排序n插入排序n归并排序n快速排序2008-09-01版权所有：杨波，武汉科技大学理学院 插入分类插入分类n基本思想for(j=2;j=n;j+)将aj放到已分类集合a1:j-1的正确位置上 2008-09-01版权所有：杨波，武汉科技大学理学院 public static void InsertionSort(int a,int n)/将a1:n中的元素按非降次序分类，n1 int i,j;/循环计数变量 int item;/欲插入数据变量 for(j=2;j=1&item6，故9置于6之后i0123456ai-693415插入“3”：36，故6，9网后移，3置于原6的位置i0123456ai-369415插入“4”：346，故6，9往后移，4置于原6的位置i0123456ai-346915插入“1”：13，故3，4，6，9均往后移，1置于原3的位置i0123456ai-134695插入“5”：456，故6，9往后移，5置于原6的位置i0123456ai-1345692008-09-01版权所有：杨波，武汉科技大学理学院 分治策略设计分治策略设计n算法的基本思想：q将分成两个集合 和q对每个集合单独分类 q将已分类的两个序列归并成一个含n个元素的分好类的序列 q这样一个分类过程称为归并分类2008-09-01版权所有：杨波，武汉科技大学理学院 归并分类算法归并分类算法void MergeSort(int low,int high)/alow:high是一个全程数组，low和high分别指示当前待分类区间的最小下标和最大下标，含有high-low+10个待分类的元素 int mid;if(lowhigh)/当含有2个及2个以上的元素时，作划分与递归处理 mid=(low+high)/2;/计算中分点 MergeSort(low,mid);/在第一个子集合上分类(递归)MergeSort(mid+1,high);/在第二个子集合上分类(递归)Merge(low,mid,high);/归并已分类的两子集合 2008-09-01版权所有：杨波，武汉科技大学理学院 使用辅助数组归并两个已分类的集合的算法使用辅助数组归并两个已分类的集合的算法public void Merge(int low,int mid,int high)int n,h,i,j,k;int b;n=a.length;b=new intn;h=low;i=low;j=mid+1;while(h=mid)&(j=high)if(ahmid)for(k=j;k=high;k+)bi=ak;i+;else for(k=h;k=mid;k+)bi=ak;i+;for(k=low;k1,c是常数化简:若n=2k,则有,T(n)=2(2T(n/4)+cn/2)+cn =4T(n/4)+2cn=4(2T(n/8)+cn/4)+2cn =2kT(1)+kcn =an+cnlogn /k=logn所以得：T(n)=O(nlogn)递归调用一直进行到子区间仅含一个元素时为止复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法2008-09-01版权所有：杨波，武汉科技大学理学院 归并分类示例归并分类示例设a=(310,285,179,652,351,423,861,254,450,520)1）划分过程划分过程310，285，179，652，351，423，861，254，450，520310，285，179，652，351423，861，254，450，520310，285，179652，351310，285179310285652351423，861，254450，520423，8612544238614505202008-09-01版权所有：杨波，武汉科技大学理学院 2）归并过程归并过程首先进入左分枝的划分与归并。第一次归并前的划分状态是：（310|285|179|652，351|423，861，254，450，520）第一次归并：（285，310|179|652，351|423，861，254，450，520）第二次归并：（179，285，310|652，351|423，861，254，450，520）第三次归并：（179，285，310|351，652|423，861，254，450，520）第四次归并：（179，285，310，351，652|423，861，254，450，520）进入右分枝的划分与归并过程（略）2008-09-01版权所有：杨波，武汉科技大学理学院 3）用树结构描述归并分类过程）用树结构描述归并分类过程1,101,56,101,34,56,89,104,43,31,12,21,25,56,78,89,910,106,67,7MergeSort(1,10)的调用1,1,26,6,71,2,34,4,56,7,89,9,101,3,56,8,101,5,10Merge的调用2008-09-01版权所有：杨波，武汉科技大学理学院 310，285，179，652，351，423，861，254，450，520310，285，179，652，351423，861，254，450，520310，285，179652，351310，285179310285652351423，861，254450，520423，861254423861450520285，310179，285，310351，652179，285，310，351，652423，861254，423，861450，520254，423，450，520，861179，254，285，310，351，423，450，520，652，8612008-09-01版权所有：杨波，武汉科技大学理学院 归并分类的非递归算法归并分类的非递归算法n设计思想2008-09-01版权所有：杨波，武汉科技大学理学院 2008-09-01版权所有：杨波，武汉科技大学理学院 public static void MergeSort(int n,int DataLength)/n为待合并数据个数为待合并数据个数 int i,t;/循环计数变量循环计数变量 i=1;/还有两段长度为还有两段长度为DataLength的的list可合并可合并 while(i=(n-2*DataLength+1)Merge(i,i+DataLength-1,i+2*DataLength-1);i=i+2*DataLength;if(i+DataLengthn)/合并两段合并两段list，一段长度为，一段长度为DataLength，另一段长度不足，另一段长度不足DataLength Merge(i,i+DataLength-1,n);else /将剩下一段长度不足将剩下一段长度不足DataLength的的list中的值不变中的值不变 2008-09-01版权所有：杨波，武汉科技大学理学院 例：要排序的数据如下i12345678910ai9876543210步骤1：length=1i12345678910ai8967452301步骤2：length=2i12345678910ai6789234501步骤3：length=4i12345678910ai2345678901步骤4：length=8i12345678910ai01234567892008-09-01版权所有：杨波，武汉科技大学理学院 改进的归并分类算法改进的归并分类算法1）算法存在的问题n 递归层次太深 在MergeSort的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。在集合含有仅相当少的元素时，较深层次的递归调用使得时间过多地消耗在处理递归上。n 元素在数组a和辅助数组b之间的频繁移动 每次归并，都要首先将a中的元素移到b中，再由b复制到a的对应位置上。2008-09-01版权所有：杨波，武汉科技大学理学院 2）改进措施n 针对递归层次问题 采用能在小规模集合上有效工作的其它算法，直接对小规模集合处理。如InsertSort算法n 针对元素频繁移动问题 采用一个称为链接信息数组Link1:n的数据结构，记录归并过程中a的元素相对于其排序后在分类表中位置坐标的链接关系。Linki取值于1，n，是指向a的元素的指针：在分类表中它指向下一个元素在a中的位置坐标。0表示表的结束。2008-09-01版权所有：杨波，武汉科技大学理学院 n例：i12345678Linki 64713080n该表中含有两个子表，0表示表的结束。n设置表头指针Q和R分别指向两个子表的起始处：Q=2，R=5；则有，表1：Q(2,4,1,6)，经过分类后有：a2a4a1a6 表2：R(5,3,7,8)，同样有：a5a3a7a8 链接信息表在归并过程中的应用：将归并过程中元素在a和b之间移动的过程变成更改Link所指示的链接关系，从而避免移动元素的本身。分类表可以通过Link的表头指针和读取Link中的链接关系取得。2008-09-01版权所有：杨波，武汉科技大学理学院 使用链接数组的归并分类模型使用链接数组的归并分类模型public static void MergeSort1(int low,int high,int p)/利用辅助数组Linklow:high将全程数组alow:high按非降次序分类。/Link中值表示按分类次序给出a下标的表，并把p置于这表开始处 if(high-low+116)InsertionSort(a,Link,low,high,p)/当规模小于16时采用插入法 else mid=(low+high)/2;MergeSort1(low,mid,q);/返回q表 MergeSort1(mid+1,high,r);/返回r表 Merge1(q,r,p);/将q和r归并成表p 2008-09-01版权所有：杨波，武汉科技大学理学院 使用链接表归并已分类的集合使用链接表归并已分类的集合 public static void Merge1(int q,int r,int p)/q和r是全程数组Link1:n中两个表的指针。这两个表可用来获得全程数组a1:n中已分类元素的子集合。此算法执行后构造出一个由p所指示的新表，利用此表可以得到按非降次序把a中元素分好类的元素表，同时q和r所指示的表随之消失。假定表由0结束 int i,j,k;i=q;j=r;k=0;/新表在Link0处开始 while(i!=0)&(j!=0)/当两表都非空时 if(ai=aj)Linkk=i;k=i;i=Linki;/找较小的关键字 else Linkk=j;k=j;j=Linkj;if(i=0)Linkk=j;else Linkk=i;p=Link0;2008-09-01版权所有：杨波，武汉科技大学理学院 MergeSort1 的调用 在初次调用时，待分类的n个元素放于a1:n中。Link1:n初始化为0；初次调用：MergeSort1(1,n,p)p作为按分类次序给出a中元素的指示表的指针。3）改进归并分类算法示例）改进归并分类算法示例 设元素表：（50，10，25，30，15，70，35，55）采用MergeSort1对上述元素表分类（不做小规模集合的单独处理）下表给出在每一次调用MergeSort1结束后，Link数组的变化情况。2008-09-01版权所有：杨波，武汉科技大学理学院 i012345678ai50 10 25 30 15 70 35 55Linki000000000qrp122201000000(10,50)343300400000(10,50),(25,30)232203410000(10,25,30,50)565503416000(10,25,30,50),(15,70)787703416080(10,25,30,50),(15,70),(35,55)575503417086(10,25,30,50),(15,35,55,70)252285473016(10,15,25,30,35,50,55,70)在上表的最后一行，p=2返回，得到链表（2，5，3，4，7，1，8，6）即：A(2)A(5)A(3)A(4)A(7)A(1)A(8)A(6)2008-09-01版权所有：杨波，武汉科技大学理学院 以比较为基础分类的时间下界以比较为基础分类的时间下界1)分类的分类的“实质实质”给定n个记录R1,R2,Rn,其相应的关键字是k1,k2,kn。分类就是确定1,2,n的一种排列P1,P2,Pn,使得记录的关键字满足以下非递减（或非递增）排列关系 kP1kP2kPn 从而使n个记录成为一个按关键字有序的序列：RP1,RP2,RPn 2008-09-01版权所有：杨波，武汉科技大学理学院 2)以关键字比较为基础的分类算法的时间下界以关键字比较为基础的分类算法的时间下界 最坏情况下的时间下界为：(nlogn)利用二元比较树证明。假设参加分类的n个关键字a1,a2,an互异。任意两个关键字的比较必导致aiaj的结果。以二元比较树描述元素间的比较过程：n 若aiaj，进入下一级的右分支2008-09-01版权所有：杨波，武汉科技大学理学院 算法在外部结点终止。从根到某外结点的路径代表某个特定输入情况下一种唯一的分类排序序列。路径长度表示生成该序列代表的分类表所需要的比较次数。而最长的路径代表算法在最坏情况下的执行情况，该路径的长度即是算法在最坏情况下所作的比较次数。故，以比较为基础的分类算法的最坏情况下界等于该算法对应的比较树的最小高度。初始集合中的元素因顺序不同，将导致排序过程走不同的分支2008-09-01版权所有：杨波，武汉科技大学理学院 由于n个关键字有n!种可能的排列，所以分类二元比较树中将有 n!个外部结点：每个外部结点代表一种特定的排列，该排列对应于某种特定输入情况下的分类序列。设一棵二元比较树的所有内结点的级数均小于或等于k，则该树中最多有2k个外结点。记算法在最坏情况下所作的比较次数为T(n)，则有T(n)=k：生成外结点所代表的分类序列所需的比较次数等于该外结点所在的级数-1；根据和的分析，有：n!2T(n)化简：当n1时，有n!n(n-1)(n-2)()(n/2)n/2 当n4时，有 T(n)(n/2)log(n/2)(n/4)logn 故，任何以比较为基础的分类算法的最坏情况的时间下界为：(nlogn)2008-09-01版权所有：杨波，武汉科技大学理学院
