#include <iostream>
#include <stdlib.h>
#define LEN 20
int a[LEN];
void merge(int ,int ,int );
void mergesort(int low,int high)
{/*利用分治思想对数组进行划分*/
int mid;
if(low<high) ///直到将每个数组分为长度为1
{
mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high); ///对两个划分数组的的合并
}
}
void merge(int low,int mid,int high)
{/*两数组的归并操作*/
int b[LEN];
int i,l,h;
i=low;
l=low;
h=mid+1;
while(l<=mid && h<=high)
{
if(a[l]<=a[h]) { b[i]=a[l]; l++;}
else {b[i]=a[h]; h++;}
i++;
}
while(l<=mid) b[i++]=a[l++];
while(h<=high) b[i++]=a[h++];
for(i=low;i<=high;i++)
a[i]=b[i];
}
void print(int *a,int n)
{
int i;
for(i=0;i<n;i++)
cout<<a[i]<<" ";
}
int main(int argc, char *argv[])
{
int n,i,s;
cout<<"请输入数组元素个数："<<endl;
cin>>n;
cout<<"请输入元素："<<endl;
for(i=0;i<n;i++)
cin>>a[i];
print(a,n);
cout<<endl;
mergesort(0,n-1);
print(a,n);
system("PAUSE");
return 0;
}
分治法：分而治之，在这个程序里，它把一个数组作为一个整体慢慢划分，直到每个元素作为一个
长度为1 的数组再进行合并。当数组共有元素N个，2^K=N，则该程序中的递归会进行K次，时间复
度为O（nlogn）,但由于在合并时采用一个辅助数组因而占用空间大，故该算法并不令人十分满
意。最近上课上的很紧，每次课下来感觉是接触到不少，只是不知道为什么，当时上课总感觉那些
经典算法都懂了，但当真正把它们变成自己的程序时总会出现这样或那样的问题，还是觉得把书本
拿出来的好，可能写的太少，懂得也太少。慢慢从编程现好好体会那些算法的用法及怎么实现的。
想到没搞定的就还有好多问题，就那矩阵相乘的动态规划还存在问题，只待慢慢解决了……