排序系列（五）---归并排序
?
//author:lilywangcn
public class MergeSort {
//private static int[] array=new int[]{10,30,20,4, 9,-1,6,15,12,8,0,20,4};
private static int[] array=new int[]{10,30,20,4,9,-1,6,15};
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
mergeSort(0,array.length-1);
}
public static void mergeSort(int left, int right){
if(left==right) return;
mergeSort(left,(left+right)/2); ?//中间的值是(left+right)/2
mergeSort((right+left)/2+1,right);
int[] tmp=new int[right-left+1]; ?//存储临时归并的结果
int i=left,j=(right+left)/2+1,k=0;//开始归并
while(i<=(right+left)/2&&j<=right){
if(array[i]<=array[j]) tmp[k++]=array[i++];
else tmp[k++]=array[j++];
}
while(i>(right+left)/2&&j<=right){
tmp[k++]=array[j++];
}
while(j>right&&i<=(right+left)/2)
tmp[k++]=array[i++];
for(int m=0;m<tmp.length;m++){
array[left+m]=tmp[m]; ? ?//将临时归并结果拷贝回数组
}
print(); ?//一次归并后的结果
}
private static void print(){
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
System.out.println("");
}
?
}
