分治法

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

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

递归经典例题：

• 阶乘函数

//迭代算法
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 );
    }
} 

版权声明：本文为博主原创文章，如有错误，恳请大家在评论区指出，在下不胜感激～如要转载注明出处即可～
本文首发于个人博客：Wonz の Blog 。