归并排序

归并排序

归并排序就是不断地将元素组分成两部分进行排序，然后进行归并。

public class Merge{ int[] arr; public void mergeSort(int[] a){ if(a==null||a.length<2) return; arr = new arr[a.length]; sort(a,0,a.length()-1); } public void sort(int[] a,int lo,int hi){ if(lo>=hi) return; int mid = lo + (hi-lo)/2; sort(a,lo,mid); //对左半部分进行排序 sort(a,mid+1,hi); //对右半部分进行排序 merge(a,lo,mid,hi); //归并 } public void merge(int[] a,int lo,int mid,int hi){ int i = lo; int j = mid+1; for(int k = lo;k<= hi;k++){//将数组a复制到arr arr[k] = a[k]; } for(int k = lo;k<=hi;k++){ if(i>mid) a[k] = arr[j++];//左用尽 else if(j>hi) a[k] = arr[i++];//右用尽 else if(a[i]>a[j]) a[k] = arr[j++]; else a[k] = arr[i++]; } } }