学步园

分治法

有很多算法在结构上是递归的：为了解决一个给定的问题，算法要一次或多次地递归调用其自身来解决相关的子问题。这些算法通常采用分治策略（divide-and-conquier）：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。分治模式在每一层递归上都有三个步骤：

²         分解（divide）：将原问题分解成一系列子问题；

²         解决（conquer）：递归地解各子问题。若子问题足够小，则直接求解；

²         合并：将子问题的结果合并成原问题的解。

自底向上的归并排序

归并排序算法完全依照分治模式，直观的操作如下：

²         分解：将n个元素分成各含n/2个元素的子序列；

²         解决：用归并排序法对两个子序列递归地排序；

²         合并：合并两个已排序的子序列以得到排序结果。

    观察下面的例子，可以发现：归并排序在分解时，只是单纯地将原问题分解为两个规模减半的子问题；在分解过程中，没有任何对原问题所含信息的利用，没有任何尝试对问题求解的动作；这种分解持续进行，直到子问题规模降足够小（为1），这时子问题直接得解；然后，自底向上地合并子问题的解，这时才真正利用原问题的特定信息，执行求解动作，对元素进行比较。

这种自底向上分治策略的编程模式如下：

    由于在自底向上的归并过程中，每一层需要进行i组n/i次比较，而且由于进行的是单纯的对称分解，总的层数总是lg n，因此，归并排序在各种情况下的时间代价都是Θ(n lg n)。试想，能够加大分组的力度，即每次将原问题分解为大于2的子问题，来降低运行时间？

下面程序的巧妙之处在于，他把两个半个数组全部复制到两个新的数组里面去，每个数组比原来多一个位置，这个多的位置干啥用呢？

用来放置哨兵，所谓的哨兵就是比数组里面明显大的的元素，因此啊在把两个数组向一个大的数组里面去拷贝的时候，不需要控制两个数组的下标，不需要判断是否一个已经越界，剩下哪个数组了，然后全部拷贝进去，会让这个程序的逻辑变得非常简单。

#include<stdio.h>
#include<stdlib.h>
#define INFINITE 1000

//对两个序列进行合并,数组从mid分开
//对a[start...mid]和a[mid+1...end]进行合并
void merge(int *a,int start,int mid,int end)
{
    int i,j,k;
    //申请辅助数组
    int *array1=(int *)malloc(sizeof(int)*(mid-start+2));
    int *array2=(int *)malloc(sizeof(int)*(end-mid+1));

    //把a从mid分开分别赋值给数组
    for(i=0; i<mid-start+1; i++)
        *(array1+i)=a[start+i];
    *(array1+i)=INFINITE;//作为哨兵
    for(i=0; i<end-mid; i++)
        *(array2+i)=a[i+mid+1];
    *(array2+i)=INFINITE;
    //有序的归并到数组a中
    i=j=0;
    for(k=start; k<=end; k++)
    {
        if(*(array1+i) > *(array2+j))
        {
            a[k]=*(array2+j);
            j++;
        }
        else
        {
            a[k]=*(array1+i);
            i++;
        }
    }
    free(array1);
    free(array2);
}

//归并排序
void mergeSort(int *a,int start,int end)
{
    int mid=(start+end)/2;
    if(start<end)
    {
        //分解
        mergeSort(a,start,mid);
        mergeSort(a,mid+1,end);
        //合并
        merge(a,start,mid,end);
    }
}

int main()
{
    int i;
    int a[7]= {0,3,5,8,9,1,2}; //不考虑a[0]
    mergeSort(a,1,6);
    for(i=1; i<=6; i++)
        printf("%-4d",a[i]);
    printf("\n");
    return 1;
}

下面这个程序是我自己写的：里面当时出现了好多错误，已经用注释表明了。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include<time.h>
#define random(x) (rand()%x)
using namespace std;

void MergeSort( int* a, int start, int end);
void  merge(int *a,int start,int mid,int end);

void printArray(int a[],int n)
{
    for(int i =0; i<n; i++)
    {
        cout<< a[i]<<" ";
    }
}
int main()
{
    while(true){
     system("cls");

    time_t t;
    int a[10]= {0};
    srand((unsigned) time(&t));
    for(int i =0; i<=9; i++)
    {
        a[i]= random(100);
    }

    //int a[10]={6,2,3,8,4,1,7,9,0,5};
    cout<<"原数组为："<<endl;
    printArray(a,10);
    MergeSort(a,0,9);
    cout<<endl<<"数组排序后为："<<endl;
    printArray(a,10);

    //int a[]  = {28,28,18};
    //merge(a,0,1,2);
    //printArray(a,3);
    cin.get();
    }
    return 0;
}
void MergeSort( int* a, int start, int end)
{

    if(start < end)
    {
        //内外不影响的
        int mid = (start + end )/2;

        MergeSort(a,start,mid);
        MergeSort(a,mid+1,end);
        merge(a,start,mid,end);
    }



}

void merge(int *a,int start,int mid,int end)
{
    int low,high;
    low = start;
    high = mid + 1;

    int *temp= new int[end - start + 1];
    int * ptr = temp;
    memset(temp,0,sizeof(temp));

    while( (low<mid+1) && (high < end +1) )
    {
        if (a[low]< a[high])
        {
            *ptr = a[low];
            low ++;
            ptr++;
        }
        else
        {
            // *temp++ = a[high++];
            *ptr = a[high];
            high++;
            ptr++;

        }
    }
    if (low > mid)
    {
        while(high < end +1)
        {
            *ptr++ = a[high++];
        }


    }
    else if (high > end)
    {
        //竟然忘记用循环了
        while(low<mid +1)
        //有疑问
        *ptr++ = a[low++];
    }

    for(int j =start; j<=end; j++)
        //竟然忘记temp参数从零开始
        a[j] = temp[j-start];

    delete []temp;
}

自顶向下的快速排序

快速排序也是基于分治策略，它的三个步骤如下：

²         分解：数组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 lg n)。如果每次分解都形成规模为n-1和0的两个子问题，快速排序的运行时间将变为Θ(n²)。快速排序的平均情况运行时间与其最佳情况相同，为Θ(n lg n)。