几种常用的排序算法之二（归并排序、未完待续）

 1 class test
 2 {
 3     static int[] cell=new int[14];
 4     
 5     public static void main(String[] args) 
 6     {
 7         int i;
 8         int[] arr={1,4,8,5,2,3,7,2,10,14,11,2,16,15};
 9 
10         mergesort(arr,0,13);
11 
12         for(i=0;i<14;i++)
13           System.out.printf("%3d",arr[i]);
14         System.out.printf("\n");
15     }
16 
17     static void mergesort(int arr[],int left,int rigth)
18     {
19        int middle;
20 
21        if(left<rigth)
22        {
23           middle=(left+rigth)/2;
24           mergesort(arr,left,middle);
25           mergesort(arr,middle+1,rigth);
26           merge(arr,left,middle,rigth);
27        }
28     }
29 
30     static void merge(int[] arr,int left,int middle,int rigth)
31     {
32        int li,ri;
33        int h;
34 
35        li=left;    
36        ri=middle+1;
37        h=left;       
38 
39        while(li<=middle && ri<=rigth)  //两个数组都剩余元素，需要比较大小
40        {
41            if(arr[li]>arr[ri])
42              cell[h++]=arr[ri++];
43            else
44              cell[h++]=arr[li++];
45        }
46 
47        while(li<=middle)            //没有遍历完的数组，则直接拷贝剩下元素，因为两个数组都是有序的
48            cell[h++]=arr[li++];
49        while(ri<=rigth)
50            cell[h++]=arr[ri++];
51 
52        for(h=h-1;h>=left;h--)//把合并好的元素拷贝回原来的数组
53            arr[h]=cell[h];       
54     }
55 }