分治法——算法总结二

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

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

问题分析：以归并排序为例子，将待排序元素分成大小大致相同的2个子集合(递归直到最小的排序单元），分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。下面我们用一张图来展示整个流程,最下面的（姑且叫他第一层）是原始数组分成了8个最小排序问题，各自只有一个元素，故不需要排序，大家可以看到，我们通过分而治之的思想把对最初数组的排序分为了若干个只有一个元素的小数组的排序,然后第二层,我们进行了合并，将每两个最小排序结果合并为有两个元素的数组,然后逐层往上进行合并，就有了最后的结果…

代码实现如下：

<pre name="code" class="objc">#include<stdio.h>
int L[100],R[100];
void merge(int numbers[],int left, int mid, int right)
        {
            int n1=mid-left+1;
            int n2=right-mid;
            int i,j,k;
            for(i=1;i<=n1;i++)
             L[i]=numbers[left+i-1];
            for( j=1;j<=n2;j++)
             R[j]=numbers[mid+j];
            L[n1+1]=99999;
            R[n2+1]=99999;
            
            i=1;
            j=1;
            
            for(k=left;k<=right;k++)
            if(L[i]<=R[j])
               {
                   numbers[k]=L[i];
                   i++;
                   }
                 else
                  {
                       numbers[k]=R[j];
                       j++;
                  }
        }

void mergeSort(int numbers[],int left, int right)

{
    if(left<right)
    {
                int mid;
            mid = (right + left) / 2;
            mergeSort(numbers, left, mid);
            mergeSort(numbers, mid+1, right);
            merge(numbers,left, mid, right);
        }

}

int main()
{
    int numbers[]={5,2,4,6,1,3,2,6};
    mergeSort(numbers,0,7);
    for(int i=0;i<8;i++)
    printf("%d",numbers[i]);
    }

class Program
    {
        
        static int[] L=new int[100];
        static int[] R=new int[100];
static void merge(int[] numbers,int left, int mid, int right)
        {
            int n1=mid-left+1;
            int n2=right-mid;
            int i,j,k;
            for(i=1;i<=n1;i++)
             L[i]=numbers[left+i-1];
            for( j=1;j<=n2;j++)
             R[j]=numbers[mid+j];
            L[n1+1]=99999;
            R[n2+1]=99999;
            
            i=1;
            j=1;
            
            for(k=left;k<=right;k++)
            if(L[i]<=R[j])
               {
                   numbers[k]=L[i];
                   i++;
                   }
                 else
                  {
                       numbers[k]=R[j];
                       j++;
                  }
        }

static void mergeSort(int[] numbers,int left, int right)

{
    if(left<right)
    {
           int mid;
            mid = (right + left) / 2;
            mergeSort(numbers, left, mid);
            mergeSort(numbers, mid+1, right);
            merge(numbers,left, mid, right);
        }

}

        public static void Main(string[] args)
        {
        int[] numbers={5,2,4,6,1,3,2,6};
        mergeSort(numbers,0,7);
        for(int i=0;i<8;i++)
        Console.Write(numbers[i]);
            
            
            // TODO: Implement Functionality Here
            
            Console.Write("Press any key to continue . . . ");
            Console.ReadKey(true);
        }
    }

归并排序算法的时间复杂度是O（nlogn）,对于冒泡排序的O(n*n),效率还有有比较好的提高。其实本人原来在学习的时候好长一段时间不理解为什么时间复杂度会是O（nlogn）,像冒泡排序就比较好理解，有两个for循环，问题的规模随着n变大而变大，算法时间复杂度自然就是O(n*n),后面花了一些时间来阅读一些资料才明白其原理，有兴趣的也可以去看看.简单的描述一下为什么会是O（nlogn）。大家看看，我们的例子，解一个8个元素的数组，我们用到了几层？是四层，假设我们这里有n个元素，我们会用到多少层？根据一定的归纳总结，我们知道我们会用到(lgn)+1层..(lgn)+1层需要用到lgn层次的合并算法.现在再看看MERGE (A, p, q, r )的复杂度是多少，毫无疑问O（n），故其归并排序的算法时间复杂度是O（nlogn）.当然这个结果还可以通过其他的方法计算出来，我这里是口语话最简洁的一种……

用归并算法，很好的解释了分治法的应用 ， 希望对您有些帮助……