许多有用的算法在结构上都是递归的，这些算法遵循分治法的思想。将原问题分解成几个规模较小的但类似于原问题的子问题，然后地柜地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。



分治模式在每层递归上都有三个步骤：


——分解原问题为若干子问题，这些子问题是原问题的规模较小的示例；

——解决这些子问题，递归地求解这些子问题。然后，若子问题的规模足够小，则直接求解；

——合并这些子问题的解成原问题的解。


归并排序算法的操作完全遵循分治模式，其操作如下：


分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列；

解决：使用归并排序递归地排序两个子序列；

合并：合并两个已经排好序的子序列以产生已排序的答案。


当待排序的序列长度为1时，递归“开始回升”，在这种情况下不要做任何工作，因为长度为1的每个序列都已经排好序。


归并排序有两种方法去实现，一种是使用哨兵牌，即在两个子数组中的末尾放置一个无穷大的哨兵牌，进而可以避免每次去判断是否已经越界；第二种方法就是需要每次去检查是否已经到达数组的边界了。


归并排序法的C语言实现


方法一：哨兵牌法

merge.c


/*
  本程序是归并法排序数组的两个部分
*/

#include<stdio.h>

#include<stdlib.h>



/*
  为了避免比较，定义两个子数组的最后一位为无穷大，使得它比数组中任意一个数都大
*/

#define infinity 10000 



/*
  排序A(p,...q)和A(p+1,...r)两个数组，其中它们各自均已排好序
*/

void merge(int *A,int p,int q,int r)

{
    int n1=q-p+1;

    int n2=r-q;


    int *L=malloc((n1+1)*sizeof(int));

    int *R=malloc((n2+1)*sizeof(int));


    int t,tmp1=0,tmp2=0;

    for(t=p;t<=q;t++) {

        *(L+tmp1)=*(A+t);

        tmp1++;

    }

    for(t=q+1;t<=r;t++) {

        *(R+tmp2)=*(A+t);

        tmp2++;

    }    

    *(L+n1)=infinity;

    *(R+n2)=infinity;


    int i=0,j=0;

    int k;


/*
  依次从两个数字中取元素，将小的放入原数组中
*/    

    for(k=p;k<=r;k++) {

        if(*(L+i)<=*(R+j)) {

            *(A+k)=*(L+i);

            i++;

        }

        else {

            *(A+k)=*(R+j);

            j++;

        }

    }

    free(L);

    free(R);

}




#include<stdio.h>

#include<stdlib.h>




void mergeSort(int *A,int p,int r)

{

    if(p<r) {

        int q=(p+r)/2;

        mergeSort(A,p,q);

        mergeSort(A,q+1,r);

        merge(A,p,q,r);

    }

}




方法二：每次检查数组是否越界

/*
  本程序是用来不用哨兵法来检查数组的边界，而是普通的通过每次询问来判断是否已经到达边界
*/

void merge1(int *A,int p,int q,int r)

{
    int n1=q-p+1;

    int n2=r-q;

    
    int *L=malloc(n1*sizeof(int));

    int *R=malloc(n2*sizeof(int));



    int i,tmp1=0,tmp2=0;



    for(i=p;i<=q;i++) {

        *(L+tmp1)=*(A+i);

        tmp1++;

    }

    for(i=q+1;i<=r;i++) {

        *(R+tmp2)=*(A+i);

        tmp2++;

    }


    int count;

        int j=0,k=0;



    for(count=p;count<=r;count++) {

        if(j==n1) {

            while(k<n2) {

                *(A+count)=*(R+k);

                count++;

                k++;

            }

            break;

        }

        if(k==n2) {

            while(j<n1) {

                *(A+count)=*(L+j);

                count++;

                j++;

            }

            break;

        }

        if(*(L+j)<=*(R+k)) {

            *(A+count)=*(L+j);

            j++;

        }

        else {

            *(A+count)=*(R+k);

            k++;

        }    

    }

}




总结

归并排序算法的代价是nlgn，其分析流程可以使用递归树来分析。归并法可以是许多相似问题的解决算法，我们可以借此联想或稍作变形即可解决类似问题。

 
 
 
来源： 张泽旺 深度学习每日摘要
智造家 查看全部