【好记性不如烂笔头】分冶算法之归并排序

 1 package com.servlet;
 2 
 3 public class MyMergeSort {
 4     public static void main(String[] args) {
 5         int[] array={2,4,7,5,8,1,3,6};
 6         printArray(array);
 7         
 8         devide(array,0,array.length-1);
 9         
10         System.out.println("排序后:");
11         printArray(array);
12     }
13     /*分解数据*/
14     public static void devide(int[] array,int left,int right){
15         
16         if(left<right){
17             /*寻找到中间下标*/
18             int mid=(right+left)/2;
19             /*从中间下标隔断，将前后两段分别分解*/
20             devide(array,left,mid);
21             /*继续分割第二段*/
22             devide(array,mid+1,right);
23             /*分割完了，调用归并*/
24             merge(array,left,mid,mid+1,right);    
25         }
26     }
27     /*归并，包含排序*/
28     public static void merge(int[] array,int leftStart,int leftEnd,int rightStart,int rightEnd){
29         /*新建临时数组，存放该次归并后的数据*/
30         int[] temp=new int[array.length];
31         /*记录归并的左组和右组开始结束下标*/
32         int ls=leftStart,le=leftEnd,
33             rs=rightStart,re=rightEnd;
34         /*记录临时数组的存放位置*/
35         int index=ls;
36         /*第一次比较归并，左组合右组中较小的入temp*/
37         while(ls<=le&&rs<=re){
38             if(array[ls]<=array[rs]){
39                 temp[index]=array[ls];
40                 index++;ls++;
41             }else{
42                 temp[index]=array[rs];
43                 index++;rs++;
44             }    
45         }
46         /*第二次选择归并，将array中剩余的未加入temp的数加入到temp中*/
47         while(ls<=le){
48             temp[index]=array[ls];
49             ls++;index++;
50         }
51         while(rs<=re){
52             temp[index]=array[rs];
53             rs++;index++;
54         }
55         /*temp是经过调整后的array，此时一次归并完毕，返回数据进行下一次归并*/
56         while(leftStart<=rightEnd){
57             array[leftStart]=temp[leftStart];
58             leftStart+=1;
59         }
60         /*打印本次归并结果*/
61         printArray(array);
62     }
63     public static void printArray(int[] array){
64         for(int i=0;i<array.length;i++)
65             System.out.print(array[i]+"  ");
66         System.out.println();
67     }
68     
69     
70 }