分治思想--小测试(归并排序后续)

 1 package cn.it;
 2 
 3 import java.util.Arrays;
 4 // 利用分治思想 实现  归并排序
 5 public class Fz {
 6     public static void main(String[] args) {
 7         int a[]={1,2,3,4,5,6,8,7,3,4,9,0};
 8         int temp[] = new int[a.length];
 9         sortdiv(a, 0, a.length-1, temp);
10         System.out.println(Arrays.toString(a));
11     }
12     
13     private static  void sortdiv(int[] a,int start,int end,int[] temp){
14         if(start<end){
15             //后序遍历 递归左子树 递归右子树 跟
16             int mid=(start+end)/2;
17             sortdiv(a, start, mid,temp);
18             sortdiv(a, mid+1, end,temp);
19             merge(a, start, end, mid,temp);
20         }
21     }
22     
23     private static void merge(int[] a,int start,int end,int mid,int[] temp){
24         int i=start;
25         int j=mid+1;
26         int k=0;
27 
28         //将较少者存入临时空间
29         while(i<=mid && j<=end){
30             if(a[i]<a[j]){
31                 temp[k++]=a[i++];
32             }else{
33                 temp[k++]=a[j++];
34             }
35         }
36         
37         //剩余的加入队尾
38         while(i<=mid){
39             temp[k++]=a[i++];
40         }
41         
42         while(j<=end){
43             temp[k++]=a[j++];
44         }
45         
46         //将有序临时数组置换回实际存储的数组
47         for(int l=0;l<k;l++){
48             a[start+l]=temp[l];
49         }
50         
51     }
52 }