public class MergeSort { public static void main(String args[]){ int[] data={ 50,49,48,47,46,45,44,43,42,41, 40,39,38,37,36,35,34,33,32,31, 30,29,28,27,26,25,24,23,22,21, 20,19,18,17,16,15,14,13,12,11, 10,9,8,7,6,5,4,3,2,1 }; /* * mergeSort(data,0,中间); * mergeSort(data,中间，最后); * merge(data,0,最后); * */ System.out.println("*********************排序前****************"); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); if(i>9 && i==0)System.out.println(); } System.out.println(); mergeSort(data,0,data.length/2); mergeSort(data,data.length/2+1,data.length-1); merge(data,0,data.length/2,data.length-1); System.out.println("*********************排序后****************"); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); if(i>9 && i==0)System.out.println(); } /*int[] data1={1,6,7,8,2,3,4,5,9}; for(int c=0;c<data1.length;c++){ System.out.print(data1[c]); } System.out.println("****************"); merge(data1,0,data1.length/2-1,data1.length-1); System.out.println("*******************"); for(int c=0;c<data1.length;c++){ System.out.print(data1[c]); } System.out.println();*/ }
public static void mergeSort(int[] data, int i, int j) { if(i<j){ mergeSort(data,i,(i+j)/2); mergeSort(data,(i+j)/2+1,j); merge(data,i,(i+j)/2,j); } }
public static void merge(int data[],int i,int m,int j){ /* * 把data[i..m]和data[m+1..j]归并 * 放到temp1[0..m-i]和temp2[0..j-m-1]中 * 归并到temp[0..j-i]中 * 然后复制到data[i..j]中 * * */ // System.out.println(i); // System.out.println(m); // System.out.println(j); int[] temp1,temp2,temp; temp1=new int[m-i+1+1]; temp2=new int[j-m-1+1+1]; temp=new int[j-i+1]; // System.out.println("数组长度:"+temp1.length+" "+temp2.length+" "+temp.length); for(int count=0;count<m-i+1;count++){ temp1[count]=data[count+i]; } temp1[m-i+1]=10000; // for(int count=0;count<temp1.length;count++){ // System.out.print(temp1[count]+" "); // } // System.out.println(); for(int count=0;count<j-m-1+1;count++){ temp2[count]=data[count+m+1]; } temp2[j-m]=10000; // for(int count=0;count<temp2.length;count++){ // System.out.print(temp2[count]+" "); // } // System.out.println(); int index1=0,index2=0; for(int count=0;count<j-i+1;count++){ if(temp1[index1]<temp2[index2]){ temp[count]=temp1[index1]; index1++; } else{ temp[count]=temp2[index2]; index2++; } } for(int count=0;count<temp.length;count++){ data[i+count]=temp[count]; } } }
