分治算法

分治是一种思想体现，就是把一个大的问题分为若干个子问题，这些子问题相互独立且与原问题性质相同然后在子问题继续向下分，一直到base cases，通过base cases的解决，一步步向上，最终解决最初的大问题。分治算法是递归的典型应用。

常见的利用分治算法思想的有 快速排序 以及 归并排序 等等。

快速排序：

又称为划分交换排序。快速排序是对冒泡排序的一种改进方法，在冒泡排序中，进行记录的关键字的比较和交换是在相邻记录之间进行，记录每次交换只能上移或者下移一个位置，而且总的比较和移动次数较多。在快速排序中。记录关键字的比较和记录的交换是从两端到中间进行的，待排序的关键字较大的就一次就能交换到后面的单元中，而关键字较小的记录一次就能够交换到前面的单元中，记录每次移动的记录较远，因此总的比较和移动次数较少，速度较快，故称为“快速排序”。(形象理解)

算法如下：

void  Partition(SeqList R ,int i, int j)
{                                         //对R[i]---R[j]区间内的记录进行一个划分排序
    RecType x=R[i];
    while(i<j){
        while(i<j&&R[j].key>=x.key)
            j--;                          //从 j 所指的位置向前搜索
        if(i<j){
          R[i] = R[j];
          i++;
        }
    while(i<j&&R[i].key<=x.key)
        i++;                              //从i所指的位置起向后搜索
    if(i<j){
        R[j]=R[i];j--;
      }
    }
   R[i] = x;
   return i;
}

有了一趟划分算法后，很容易写出快速排序的递归算法

void QuickSort(SeqList  R, int low, int high)
{
    int p;
    if(low<high){
         p = Partition(R, low,high);
         QuickSort(R, low,p-1);
         QuickSort(R, p+1,high);
    }
}  

从排序结果来看，快速排序是不稳定的，一般来说，快速排序有非常好的时间复杂度，它由于其他各种排序算法。可以证明，对n个记录进行快速排序的平均时间复杂度为O(nlog2n)。但是当待排序文件的记录已按照关键字有序或者基本有序时,复杂度反而增大了，原因是在第一趟快速排序中经过n-1次比较后，第一个记录仍然在它原来的位置上，并得到一个包含n-1个记录的子文件，第二次递归调用，经过n-2次比较，第二个记录仍定位在它原来的位置上，从而得到一个包括n-2个记录的子文件。以此类推。
这使得快速排序转变成冒泡排序，其时间复杂度为O(n²)。在这种情况下，可以对排序算法加以改进。从时间上分析，快速排序比其他排序算法要快；但从空间来看，由于快速排序的过程是递归的，因此需要一个栈空间实现递归，栈的大小取决于递归调用的深度。，栈的最大深度为[log2n]+1, 即使在最坏的情况下，栈的最大深度也不会超过n。因此，快速排序需要附加的空间为O(log2n)。

归并排序

归并排序的基本思想是：首先将待排序的文件看成n个长度为1的有序子文件，把这些子文件两两归并，得到n/2个长度为2的有序子文件；然后再把这n/2个有序的子文件两两归并，如此反复，最后得到一个长度为n的有序文件为止。这种排序方法称为二路归并排序。

二路归并排序中的核心操作是将数组中前后两个相邻的有序序列鬼秉承一个有序序列，其算法如下：

void Merge(SeqList R, SeqList MR, int low,int m, int high)
{
      int i,j,k;
      i = low; j=m+1;k=low;                    //初始化
      while(i<m &&j<= high)
          if(R[i].key<=R[j].key)
                MR[k++]=R[i++];
          else
                MR[k++]=R[j++];                 //将R[low..m]中剩余的复制到MR中
       while(j<=high)
                MR[k++] = R[j++];               //将R[m+1..high]中剩余的复制到MR
}

一趟归并排序的基本思想是，在某趟排序归并中，设各子文件长度为len(最后一个子文件长度可能会小于len)，则归并前R[1..n]中共有[n/len]个有序子文件。调用归并操作对子文件进行归并时，必须对子文件的个数可能是奇数，最后一个子文件的长度可能小于len这两种特殊情况进行处理：若子文件个数为奇书，则最后一个子文件无需和其他子文件归并；若子文件个数为偶数，则要注意最后一对子文件中后一个子文件的区间上界为n。具体的一趟归并排序算法如下:

void  MergePass(SeqList  R, SeqList  MR, int len, int n)
{
      int i,j;
      for(i=1;i+2*len-1<=n;i=i+2*len)
            Merge(R,MR,i,i+len-1,i+2*len-1);
      if(i+len-1<n)                    //尚有两个子文件，其中最后一个长度小于len
            Merge(R,MR,i,i+len-1,n);     
      else                              //文件个数为奇数，最后一个子文件复制到MR中
            for(j=i;j<=n;j++)
                MR[j]=R[j];

}

整个归并排序算法如下：

void MergeSort()
{
      int len = 1;
      while(len<n)
           MergePass(R,MR,len,n);
           len = len*2;
           MergePass(MR,R,len,n);
           len = len*2;

}

二路归并排序的过程需要进行[log2n]趟。每一趟归并排序的操作，等于将两个有序子文件进行归并，而每一对有序子文件归并时，记录的比较次数均小于等于记录的移动次数，记录移动的次数均等于文件中记录的个数n，即每一趟归并的时间复杂度为0(n)。因此，二路归并的时间复杂度为O(nlog2n)。