而结构不原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到原问题的解。容易确定运行时间,是分治算法的有点之一。6.分治模式在每一层递归上都有三个步骤:分解(Divide):将原问题分解成一系列子问题;解决(Conquer):递归地解各子问题。若子问题足够小,则直接求解;bine):将子问题的结果合并成原问题的解。7.合并排序(MergeSort)算法完全依照了分治模式。分解:将n个元素分成各含n/2个元素的子序列;解决:用合并排序法对两个子序列递归地排序;合并:合并两个已排序的子序列以得到排序结果。在对子序列排序时,其长度为1时递归结束。单个元素被视为是已排好序的。合并排序的关键步骤在于合并步骤中的合并两个已排序子序列。为做合并,引入一个辅助过程MERGE(A,p,q,r),其中A是个数组,p、q和r是下标,满足p≤q<。该过程假设子数组A[p..q]和A[q+1..r]都已排好序,并将他们合并成一个已排好序的子数组代替当前子数组此笔记尚未定稿如果问题和建议请联系zhangshuijing@欢迎指教9MERGE过程:MERGE(A,p,q,r)1n1←q?p+12n2←r?q3createarraysL[1..n1+1]andR[1..n2+1]4fori←1ton15doL[i]←A[p+i-1]6forj←1to?7doR[j]←A[q+j]8L[n1+1]←∞9R[n2+1]←∞10i←111j←112fork←ptor13doifL[i]≤R[j]14thenA[k]←L[i]15i←i+116elseA[k]←R[j]17j←j+1MERGE过程正确性的证明初始化:第一轮循环,k=p,i=1,j=1,已排序数组L、R,比较两数组中最小元素L[i]、R[j],取较小的置于A[p],此时子数组A[p..p]丌仅是已排序的(仅有一个元素),而且是所有待排
全文预览
