文档介绍：归并排序可以运用分而治之方法来解决排序问题,该问题是将n个元素排成非递减顺序。分而治之方法通常用以下的步骤来进行排序算法:若n为1,算法终止;否则,将这一元素集合分割成两个或更多个子集合,对每一个子集合分别排序,然后将排好序的子集合归并为一个集合。假设仅将n个元素的集合分成两个子集合。现在需要确定如何进行子集合的划分。一种可能性就是把前面n-1个元素放到第一个子集中(称为A),最后一个元素放到第二个子集里(称为B)。按照这种方式对A递归地进行排序。由于B仅含一个元素,所以它已经排序完毕,在A排完序后,只需要用程序2-10中的函数insert将A和B合并起来。把这种排序算法与InsertionSort(见程序2-15)进行比较,可以发现这种排序算法实际上就是插入排序的递归算法。该算法的复杂性为O(n2)。把n个元素划分成两个子集合的另一种方法是将含有最大值的元素放入B,剩下的放入A中。然后A被递归排序。为了合并排序后的A和B,只需要将B添加到A中即可。假如用函数Max(见程序1-31)来找出最大元素,这种排序算法实际上就是SelectionSort(见程序2-7)的递归算法。假如用冒泡过程(见程序2-8)来寻找最大元素并把它移到最右边的位置,这种排序算法就是BubbleSort(见程序2-9)的递归算法。这两种递归排序算法的复杂性均为(n2)。若一旦发现A已经被排好序就终止对A进行递归分割,则算法的复杂性为O(n2)(见例2-16和2-17)。上述分割方案将n个元素分成两个极不平衡的集合A和B。A有n-1个元素,而B仅含一个元素。下面来看一看采用平衡分割法会发生什么情况:A集合中含有n/k个元素,B中包含其余的元素。递归地使用分而治之方法对A和B进行排序。然后采用一个被称之为归并(merge)的过程,将已排好序的A和B合并成一个集合。例2-5考虑8个元素,值分别为[10,4,6,3,8,2,5,7]。如果选定k=2,则[10,4,6,3]和[8,2,5,7]将被分别独立地排序。结果分别为[3,4,6,10]和[2,5,7,8]。从两个序列的头部开始归并这两个已排序的序列。元素2比3更小,被移到结果序列;3与5进行比较,3被移入结果序列;4与5比较,4被放入结果序列;5和6比较,.。如果选择k=4,则序列[10,4]和[6,3,8,2,5,7]将被排序。排序结果分别为[4,10]和[2,3,5,6,7,8]。当这两个排好序的序列被归并后,即可得所需要的排序序列。图2-6给出了分而治之排序算法的伪代码。算法中子集合的数目为2,A中含有n/k个元素。templatevoidsort(TE,intn){//对E中的n个元素进行排序,k为全局变量if(n>=k){i=n/k;j=n-i;令A包含E中的前i个元素令B包含E中余下的j个元素sort(A,i);sort(B,j);merge(A,B,E,i,j,);//把A和B合并到E}else使用插入排序算法对E进行排序}图14-6分而治之排序算法的伪代码从对归并过程的简略描述中,可以明显地看出归并n个元素所需要的时间为O(n)。设t(n)为分而治之排序算法(如图14-6所示)在最坏情况下所需花费的时间,则有以下递推公式:其中c和d为常数。当n/k≈n-n/k时,t(n)的值最小。因此当k=2时,也就是说,当两个子