分治法的思想是将原问题分解为几个规模小的同类问题,递归地求解这些子问题,然后再将子问题的解合并去解决原问题。
分治法每层递归可以分为三个步骤:
1.分解:将大的问题分解成同类型的小问题
2.解决:递归解决各个子问题,直到当前子问题无法继续分割或者小于某个规模
3.合并:将分割后的子问题的解依次合并,组成原问题的解
书上举的例子的归并排序,并且将归并排序的过程用文字描述了出来:
分解:将待排序的n个元素的序列分解成各具n/2个元素的两个子序列
解决:使用归并排序递归地将排序两个子序列
合并:合并两个已经排序的子序列以产生已排序的答案
下面是书中给出的伪代码:
MERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q let L[1..n1+1] and R[1...n2+1] be new arrays for i = 1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q+j] L[n1+1] = ∞ R[n2+1] = ∞ i = 1 j = 1 for k = p to r if L[i] <= R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1 MERGE-SORT(A, p, r) if p < r q = ⌊(p+r)/2⌋ MERGE-SORT(A,p,q) MERGE-SORT(A,q+1,r) MERGE(A,p,q,r)
解释一下上面的伪代码中的一些细节,L[n1+1]和R[n2+1]=∞是为了在当前位置终止,不再继续往后进行比较防止数组越界;MERGE-SORT中先调用两个SORT函数后调用MERGE函数是为了保证前后数组各自是有序的,才能保证合并后的数组是有序的当子数组长度为1时必定有序,所以可以进行合并。
将代码换成注释重新填写一遍:
void merge(---){//传入相关参数(数组,起始坐标) //定义变量表示中间值左右数的数量,定义数组并存放排好序的子数组 //将定义的数组以大于数组极大值结尾防止数组越界 //定义两个指针对数组对应位置的数进行比较,将大的(小的)存放进原数组 } void merge_sort(---){//传入相关参数(数组,起始坐标) //当长度大于1时将数组分成两份,分别对两份子数组进行排序(递归操作),然后再将两个数组合并 }
最后将注释部分补全,这里用c++举例子:
void merge(int* A, int p, int q, int r){ /* A:要进行合并的数组 p:第一个子数组的起点 q:第二个子数组的起点 r:第二个子数组的终点 */ int n1 = q - p; int n2 = r - q; int L[100], R[100]; for(int i = 0; i < n1; i++) L[i] = A[p + i]; for(int i = 0; i < n2; i++) R[i] = A[q + i]; L[n1] = 1e9+7; R[n2] = 1e9+7; int i = 0, j = 0; for(int k = p; k < r; k++){ if(L[i] <= R[j]) A[k] = L[i++]; else A[k] = R[j++]; } } void merge_sort(int* A, int p, int r){ /* A:要进行排序的数组 p:数组要排序的部分的起点 r:数组要排序的部分的终点 */ if(p < r-1){ int q = (p+r) / 2; merge_sort(A, p, q); merge_sort(A, q, r); merge(A, p, q, r); } }