|
自顶向下的方法 采用分治法进行自顶向下的算法设计形式更为简洁 ()分治法的三个步骤 设归并排序的当前区间是R[lowhigh]分治法的三个步骤是 ①分解将当前区间一分为二即求分裂点 ②求解递归地对两个子区间R[lowmid]和R[mid+high]进行归并排序; ③组合将已排序的两个子区间R[lowmid]和R[mid+high]归并为一个有序的区间R[lowhigh] 递归的终结条件子区间长度为(一个记录自然有序) ()具体算法 void MergeSortDC(SeqList Rint lowint high) {//用分治法对R[lowhigh]进行二路归并排序 int mid; if(low mid=(low+high)/2; //分解 MergeSortDC(R，low，mid); //递归地对R[low..mid]排序 MergeSortDC(R，mid+1，high); //递归地对R[mid+1..high]排序 Merge(R，low，mid，high); //组合，将两个有序区归并为一个有序区 } }//MergeSortDC (3)算法MergeSortDC的执行过程 算法MergeSortDC的执行过程如下图所示的递归树。Tw.WInGwiT.CoM 二、算法分析 1、稳定性 归并排序是一种稳定的排序。 2、存储结构要求 可用顺序存储结构。也易于在链表上实现。 3、时间复杂度 对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均 是O(nlgn)。 4、空间复杂度 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。 注意： 若用单链表做存储结构，很容易给出就地的归并排序。具体【参见练习】。 |
