分治法(归并排序、快速排序)

• 该问题的规模缩小到一定的程度就可以容易地解决；
• 该问题可以分解为若干个规模较小的相同问题;
• 分解出的子问题的解可以合并为原问题的解；
• 分解出的各个子问题是相互的。

经典问题

int BSearch(int a[],int x, int low, int high){
  int mid;
  if(low>high) return -1;
  if(x==a[mid]) return mid;
  if(x<a[mid]) return(BSearch(a,x,low,mid-1));
  else return(BSearch(a,x,mid+1,high));
}

int BSearch(int a[],int key, int n){
  int low, high, mid;
  low=0;high = n-1;
  while(low<=high){
    mid =(low+high)/2;
    if(a[mid]==key) return mid;
    else if(a[mid]<key) low=mid+1;
    else high = mid -1;  
  }
  return -1;
}

例题

int rotateBinarySearch(int a[],int aLength, int key){
}

int rotateBinarySearch(int a[],int aLength, int key){
  int low =0;
  int high = aLength-1;
  while(low<=high){
    int mid = low + ((high-low)>>1);
	if(a[mid]==key) return mid;
	if(a[low]<=a[mid]){//低端有序
	  if(key>a[low]&&key<a[mid]) high = mid -1;
	  else low = mid +1;
	}
	else //高端有序
	{
	  if(key<a[mid]&&key<=a[high])
	    low = mid +1;
	  else
	    high = mid -1;
	}
  }
}

//将有二个有序数列a[first...mid]和a[mid...last]合并。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
	int i = first, j = mid + 1;
	int m = mid,   n = last;
	int k = 0;
	
	while (i <= m && j <= n)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	
	while (i <= m)
		temp[k++] = a[i++];
	
	while (j <= n)
		temp[k++] = a[j++];
	
	for (i = 0; i < k; i++)
		a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		mergesort(a, first, mid, temp);    //左边有序
		mergesort(a, mid + 1, last, temp); //右边有序
		mergearray(a, first, mid, last, temp); //再将二个有序数列合并
	}
}

bool MergeSort(int a[], int n)
{
	int *p = new int[n];
	if (p == NULL)
		return false;
	mergesort(a, 0, n - 1, p);
	delete[] p;
	return true;
}

• 分解：数组A[p..r]被划分成两个（可能空）子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每个元素都小于等于A(q)，而且，小于等于A[q+1..r]中的元素。下标q也在这个划分过程中进行运算。
• 解决：通过递归调用快速排序，对子数组A[p..q-1]和A[q+1..r]排序
• 合并：因为两个子数组是就地排序的，将他们合并不需要操作:整个数组A[p..r]已排序。

问题：在n个元素中找出最大值和最小值。

 void  MaxMin(Type a[],int n,Type &max,Type &min)
{
    max=min =a[0];
    for(int i=1;i<n;i++)
            {  if(a[i]>max) max=a[i];
               if(a[i]<min)  min=a[i];
            }
} 

void MaxMin(int i,int j,Type &max,Type &min)
{   
       if(i==j) max=min=a[i];//分解的最小问题
       else if(i==j-1){//分解的另一种的最小问题
                      if(a[i]<a[j]){  max=a[j];min=a[i];}
                      else{max=a[i];min=a[j];}
                     }
      else {
           int mid=(i+j)/2;
           Type max1,min1;
          //分解成子问题
           MaxMin(i,mid,max,min);
           MaxMin(mid+1,j,max1,min1);
           // 合并子问题的解     
           if(max<max1) max=max1;
           if(min<min1) min=min1;
           }
}