归并排序采用的是分治的思想，首先divide，把数组二分，然后再合并分开的两个数组，这里和并的两个数组分别都是有序的。合并后让整个start和end区间内的数组有序。
public static void main(String[] args) { int [] arr = {1,1,1,1,1,1,2,1,1,1,1,1,1,1}; int [] tmp = new int[arr.length] ; divide(arr,0,arr.length-1,tmp); for(int i:arr){ System.out.PRint(i+" "); } } private static void divide(int[] arr, int start, int end,int [] tmp) { if(start < end){ int mid = (start+end)/2; divide(arr,start,mid,tmp); divide(arr,mid+1,end,tmp); merge(arr,start,mid,end,tmp); } return ; } private static void merge(int[] arr, int start, int mid, int end,int [] tmp) { int i = start; int j = mid +1; int k = 0; while(i <= mid && j <= end){ if(arr[i] <= arr[j]){ tmp[k++] = arr[i++]; }else{ tmp[k++] = arr[j++]; } } while(i <= mid){ tmp[k++] = arr[i++]; } while(j <= end){ tmp[k++] = arr[j++]; } for(i = 0 ; i < k;i++){ arr[start+i] = tmp[i]; } }新闻热点
疑难解答
