归并排序

将一个数组，先分后整合的过程 先分成 8 4 2 1 然后根据数据大小顺序 1 2 4 8 进行组合
如图所示：

通过递归来分解 public void sort(int a[],int low,int high) { if (low<high) { int mid=(low+high)/2; sort(a,low,mid); sort(a,mid+1,high); mergesort(a,low,high,mid); } } 在分解结束后调用 mergesort(a,low,high,mid); mergesort(a,low,high,mid); 函数进行整合
public void mergesort(int a[],int low,int high,int mid) { int c[]=new int [a.length]; //创建一个数组用于排序 int lowtemp=low; int midtemp=mid+1; int tempadr=low; //c数组下标 while (lowtemp<=mid&&midtemp<=high) //两个字段进行整合 { if (a[lowtemp]<=a[midtemp]) c[tempadr++]=a[lowtemp++]; else c[tempadr++]=a[midtemp++]; } /**上述整合时如果一个子段排序完成就会推出循环 所以下面

将剩下有序的数组放入到a数组中 * * / while (midtemp<=high) c[tempadr++]=a[midtemp++]; while(lowtemp<=mid) c[tempadr++]=a[lowtemp++]; /*将排序好的数据放入到a数组中
*/ for (int i=low;i<=high;i++) a[i]=c[i]; }