分治法_牛客博客

分治法——将一个复杂的问题分解成若干个规模较小、相互独立，但类型相同的子问题求解；然后再将各子问题的解组合成原始问题的一个完整答案，这样的问题求解策略就叫分治法。

设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

递归经典例题：

阶乘函数

//迭代算法
int factLoop(int n)
{ 	int k,f;
	k=1;
	f=1;
	while (kn)
	{
	 	int f=f*k;
		int k=k+1;
	}
	return f;
}

//递归算法
int factRec(int n)
{
   if (n==0)
    	return 1;
    else
        return n*factRec(n-1);
}

Fibonacci 数列

无穷数列 1，1，2，3，5，8，13，21，34，55，……，称为 Fibonacci 数列。它可以递归地定义为：

//第n个Fibonacci数可递归地得到
int fib(int n)
{
    if (n <= 1)
	    return 1;
    else
        return fib(n-1)+fib(n-2);
}

Hanoi 塔问题

设 a,b,c 是 3 个塔座。开始时，在塔座 a 上有一叠共 n 个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为 1,2,…,n,现要求将塔座 a 上的这一叠圆盘移到塔座 b 上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：

规则 1：每次只能移动 1 个圆盘；

规则 2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

规则 3：在满足移动规则 1 和 2 的前提下，可将圆盘移至 a,b,c 中任一塔座上。

void hanoi(int n, int a, int b, int c)	     //从a移到b(借助c)
{
       if (n > 0)
       {
          hanoi(n-1, a, c, b);
          move(a,b);
          hanoi(n-1, c, b, a);
       }
}

T(1) = 1

T(n) = 2T(n-1) +1

2T(n-1) = 4T(n-2) + 2

4T(n-2) = 8T(n-3) + 4

…….

2n-2T(2) = 2n-1T(1) + 2n-2

T(n) = 2^n - 1

递归小结

优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。

缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。

对半搜索

//递归算法
template<class T> 
int SortableList<T>:BSearch(const T& x, int left, int right)const
{
      if (left<=right){
	int m=(left+right)/2;		// 对半分割：m=(left+right)/2
	if (x<l[m]) return BSearch(x,left,m-1);		//搜索左半子表
	else if (x>l[m]) return BSearch(x,m+1,right);	//搜索右半子表
		else return m;	
      }
      return -1;			
} 

//迭代算法
template<class T> 
int SortableList<T>:BSearch(const T& x)const
{
   int m,left=0,right=n-1;
    while (left<=right){ 
        	m = (left+right)/2;		//对半分割
        	if (x<l[m]) right=m-1;		//搜索左半子表
        	else if (x>l[m]) left=m+1;	//搜索右半子表
		else return m;		//搜索成功
        }
    return -1;				//搜索失败
}

折半插入排序

基本思想：设在顺序表中有一个对象序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的对象。在插入 V[i] 时, 利用对半搜索寻找 V[i] 的插入位置。

typedef int T; 

void BInsSort ( T V[ ], int n ) {
   T temp;  
   int Left, Right;    
   for ( int i = 1; i < n; i++) {
        	Left = 0;  Right = n-1;  temp = V[i];
        	while ( Left <= Right ) {		//对半搜索		
            	int mid = ( Left + Right )/2;		
           		if ( temp < V[mid] ) 	Right = mid - 1;
		else 	Left = mid + 1;
        	}
   	for ( int k = i-1; k >= Left; k-- ) V[k+1] = V[k];//记录后移
   	V[Left] = temp; //插入
   }
}

两路合并排序

void MergeSort()
{	
    MergeSort(0,n-1);
}
void MergeSort(int left,int right)
{
	if (left<right) {	//序列长度大于1时，进一步划分
		int mid=(left+right)/2;	//一分为二
		MergeSort(left,mid);	//对左子序列元素排序
		MergeSort(mid+1,right);	//对右子序列元素排序
		Merge(left,mid,right);	
		//将已排好序的左、右子序列合并成一个有序序列
}
    
void Merge (int left,int mid,int right)
{    T* temp=new T[right-left+1]; 
      int k=0; 		      //k为数组temp中当前位置
      int i=left,	j=mid+1;  //i为左子序列当前位置；j为右子序列当前位置
      while ((i<=mid) && (j<=right))
	if (l[i]<=l[j])	temp[k++]=l[i++];
	else 	temp[k++]=l[j++];
      while (i<=mid) temp[k++]=l[i++];
      while (j<=right) temp[k++]=l[j++];
      for (i=0,k=left;k<=right;) l[k++]=temp[i++];
					        //从temp中重新写回序列l中
}

快速排序

void QuickSort(int left,int right)
{	if (left<right){ 	//当序列长度>1时，用Partition函数分割
		int j=Partition(left,right);	//对序列进行分划操作
		QuickSort(left,j-1);		//对左子序列进行快速排序
		QuickSort(j+1,right);	//对右子序列进行快速排序
	}
}

int Partition(int left,int right)
{	//调用本函数的前置条件：left<right；主元为第一个元素l[left] 。
	int i=left,j=right+1;
	do{	do i++; while (l[i]<l[left]);	// 从l[left+1]开始比较
			// i右移，直到遇到一个不小于主元的元素停止
		do j--; while (l[j]>l[left]);	//  从l[right]开始比较
			// j左移，直到遇到一个不大于主元的元素停止
		if (i<j) Swap(i,j);	//交换l[i]和l[j]两个元素
	}while (i<j); 			//只要i仍小于j
	Swap(left,j);	//最后将主元l[left]与l[j] 交换，结束一趟分划操作
	return j;	//返回当前主元的位置
}

采用随机选择策略的快速排序算法 RandomizedPartition

int RandomizedPartition (int left, int right)
{       int i = Random(left,right);
        Swap(i, left);
        return Partition(left, right);		//再调用Partition函数
}

如何选出n个元素中第k小的元素？（模拟快速排序算法设计）

每一步根据一个随机选取的元素对输入数组进行递归划分，

只对含有第k小元素的那部分子数组进行递归操作

——寻找x[k]位置的所有者。

template <class Type>
Type RandomizedSelect(Type a[],int p,int r,int k)
{//在数组a中下标从p到r的范围内查找第k小的元素
	if (p==r) return a[p];	//a[p]即是第k小的元素
	int i=RandomizedPartition(a,p,r);
			//快速排序的一趟分划操作
	j=i-p+1; //前面子数组中（包括位置i处）元素总数
	if (k<=j) 
		return RandomizedSelect(a,p,i,k);
	else 
		return RandomizedSelect(a,i+1,r,k-j);
}

希尔排序

typedef int SortData;
void ShellSort ( SortData V[], int n ) {
    SortData temp;  int gap = n / 2;    //gap是间隔
    while ( gap != 0 ) 	          //循环,直到gap为零
    {  
         for ( int i = gap; i < n; i+=gap)
         {  
             temp = V[i];	          //直接插入排序
             for ( int j = i; j >= gap; j = j-gap )
                    if ( temp < V[j-gap] )  V[j] = V[j-gap];
                    else break;  
	         V[j] = temp;
          }				
         gap = ( int ) ( gap / 2 );
    }
}