问题：应用归并法对一个记录序列进行升序排序（利用分治法） 思路：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.划分 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;}