分治法-归并排序

问题：应用归并法对一个记录序列进行升序排序（利用分治法）

思路：1.划分
      2.求解子问题
      3.合并

归并排序的执行过程：（*是拆分，#是合并）

     8  3  2  6  7  1  5  4
  *8 3 2 6*         *7 1 5 4*
*8 3*  *2 6*      *7 1*  *5 4*
*8* *3* *2* *6*  *7* *1* *5* *4*
#3 8#   #2 6#    #1 7#   #4 5#
#2 3 6 8#           #1 4 5 7#
    1  2  3  4  5  6  7  8

如果还不理解什么是“归并排序”，请查看百度百科或者《数据结构》
这里不再多说，主要实现分治的解决方法

实现代码：（数据上限：n<=1000）

#include<stdio.h>
int r[1010]; 
void Merge(int r[],int r1[],int s, int m,int t)//合并子序列 
{
     int i=s,j=m+1,k=s;
     while(i<=m&&j<=t)
     {
        if(r[i]<=r[j]) r1[k++]=r[i++];//取r[i]h和r[j]中较小者放入r1[k] 
        else r1[k++]=r[j++];
     } 
     while(i<=m)//若第一个子序列没有处理完，则进行收尾处理 
        r1[k++]=r[i++];
     while(j<=t)//若第二个子序列没有处理完，则进行收尾处理 
        r1[k++]=r[j++];
}
void MergeSort(int r[],int s,int t)//对序列r[s]~r[t]进行归并排序 
{
     int i,m,r1[1010];
     if(s==t) return;
     else
     {
         m=(s+t)/2;
         MergeSort(r,s,m);//求解子问题1，归并排序前半个子序列 
         MergeSort(r,m+1,t);//求解子问题2，归并排序前半个子序列 
         Merge(r,r1,s,m,t);//合并两个有序子序列，结果保存在数组r1中 
         for(i=s;i<=t;i++)//将有序序列传回r中 
         r[i]=r1[i];
     }
} 
int main()
{
    int i,j,n,m;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&r[i]);
    MergeSort(r,0,n-1);
    for(i=0;i<n;i++)
    printf("%d ",r[i]);
    puts("");
    return 0;
}