资源描述
2008-09-01,版权所有：杨波，武汉科技大学理学院,第四章分治法,2008-09-01,版权所有：杨波，武汉科技大学理学院,4.4归并分类,分类问题排序对一个给定含有n个元素（又称为关键字）的集合，按一定次序进行分类（如非降次序）称n元排序。常见的排序方法：冒泡排序插入排序归并排序快速排序,2008-09-01,版权所有：杨波，武汉科技大学理学院,插入分类,基本思想for(j=2;j6，故9置于6之后,插入“3”：36，故6，9网后移，3置于原6的位置,插入“4”：346，故6，9往后移，4置于原6的位置,插入“1”：13，故3，4，6，9均往后移，1置于原3的位置,插入“5”：456，故6，9往后移，5置于原6的位置,2008-09-01,版权所有：杨波，武汉科技大学理学院,分治策略设计,算法的基本思想：,将,分成两个集合,和,对每个集合单独分类,将已分类的两个序列归并成一个含n个元素的分好类的序列,这样一个分类过程称为归并分类,2008-09-01,版权所有：杨波，武汉科技大学理学院,归并分类算法,voidMergeSort(intlow,inthigh)/alow:high是一个全程数组，low和high分别指示当前待分类区间的最小下标和最大下标，含有high-low+10个待分类的元素intmid;if(lowhigh)/当含有2个及2个以上的元素时，作划分与递归处理mid=(low+high)/2;/计算中分点MergeSort(low,mid);/在第一个子集合上分类(递归)MergeSort(mid+1,high);/在第二个子集合上分类(递归)Merge(low,mid,high);/归并已分类的两子集合,2008-09-01,版权所有：杨波，武汉科技大学理学院,使用辅助数组归并两个已分类的集合的算法,publicvoidMerge(intlow,intmid,inthigh)intn,h,i,j,k;intb;n=a.length;b=newintn;h=low;i=low;j=mid+1;while(hmid)for(k=j;k=high;k+)bi=ak;i+;elsefor(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，520,310，285，179，652，351,423，861，254，450，520,310，285，179,652，351,310，285,179,310,285,652,351,423，861，254,450，520,423，861,254,423,861,450,520,2008-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）用树结构描述归并分类过程,2008-09-01,版权所有：杨波，武汉科技大学理学院,310，285，179，652，351，423，861，254，450，520,310，285，179，652，351,423，861，254，450，520,310，285，179,652，351,310，285,179,310,285,652,351,423，861，254,450，520,423，861,254,423,861,450,520,285，310,179，285，310,351，652,179，285，310，351，652,423，861,254，423，861,450，520,254，423，450，520，861,179，254，285，310，351，423，450，520，652，861,2008-09-01,版权所有：杨波，武汉科技大学理学院,归并分类的非递归算法,设计思想,2008-09-01,版权所有：杨波，武汉科技大学理学院,2008-09-01,版权所有：杨波，武汉科技大学理学院,publicstaticvoidMergeSort(intn,intDataLength)/n为待合并数据个数inti,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，另一段长度不足DataLengthMerge(i,i+DataLength-1,n);else/将剩下一段长度不足DataLength的list中的值不变,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：要排序的数据如下,步骤1：length=1,步骤2：length=2,步骤3：length=4,步骤4：length=8,2008-09-01,版权所有：杨波，武汉科技大学理学院,改进的归并分类算法,1）算法存在的问题递归层次太深在MergeSort的执行过程中，当集合仅含有两个元素时，仍要进一步做递归调用，直至每个集合仅含有一个元素时才退出递归调用。在集合含有仅相当少的元素时，较深层次的递归调用使得时间过多地消耗在处理递归上。元素在数组a和辅助数组b之间的频繁移动每次归并，都要首先将a中的元素移到b中，再由b复制到a的对应位置上。,2008-09-01,版权所有：杨波，武汉科技大学理学院,2）改进措施针对递归层次问题采用能在小规模集合上有效工作的其它算法，直接对小规模集合处理。如InsertSort算法针对元素频繁移动问题采用一个称为链接信息数组Link1:n的数据结构，记录归并过程中a的元素相对于其排序后在分类表中位置坐标的链接关系。Linki取值于1，n，是指向a的元素的指针：在分类表中它指向下一个元素在a中的位置坐标。0表示表的结束。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：,该表中含有两个子表，0表示表的结束。设置表头指针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,版权所有：杨波，武汉科技大学理学院,使用链接数组的归并分类模型,publicstaticvoidMergeSort1(intlow,inthigh,intp)/利用辅助数组Linklow:high将全程数组alow:high按非降次序分类。/Link中值表示按分类次序给出a下标的表，并把p置于这表开始处if(high-low+11时，有n!n(n-1)(n-2)()(n/2)n/2当n4时，有T(n)(n/2)log(n/2)(n/4)logn故，任何以比较为基础的分类算法的最坏情况的时间下界为：(nlogn),
展开阅读全文