归并排序--java

一、描述
   1，数组中的每个元素视为一个有序表(共有n个有序表)
   2，每相邻的两个有序表进行归并，生成一个新的有序表
   3，当下一次归并的个数为0时结束（即mid=size/(len<<1)）len为当前有序表的长度--------因为每次归并需要两个长度为len的有序表，当条件不满足时，便会结束，（mid表示当前有几对有序表）

class merge
{
	//对两个有序表进行归并
	//s start,m middle, t terminal---a[s]--a[m-1]为一个有序表；a[m]-a[t]为一个有序表
	public static void merge(int a[],int s,int m,int t){
		//临时表用于存放对这两张表归并后的列表
		int temp[] =new int[t-s+1];
		//i,j分别为指向两个列表的指针
		int i=s,j=m,k=0;
		while (i<m && j<=t)
		{
			if(a[i]>a[j]){
				temp[k++]=a[j++];
			}else{
				temp[k++]=a[i++];
			}
		}	
		//左边还有剩余
		while(i<m){
			temp[k++]=a[i++];
		}
		//右边还有剩余
		while(j<=t){
			temp[k++]=a[j++];
		}
		//将归并好的有序列表temp考贝到原列表a中
		System.arraycopy(temp,0,a,s,temp.length);
	}
	public static void mergeSort(int[] a,int len){
		//len 是每个有序集合的长度
		int size=a.length;
		int mid=size/(len<<1);//当前有mid对有序表（每张有序表的长度为len）
		int c=size&((len<<1)-1);//c是余数，与运算都为1时才为1；len是2的n次方，(len<<1-1)表示len位上有n个1------指除了mid对有序表外剩下的数据

		int s=0;
		for(int i=0;i<mid;i++){
		   s=i*2*len;//每一个有序集合是要跟相邻的集合进行归并
		   merge(a,s,s+len,s+(len<<1)-1);
		}
		if(c !=0){
			//有一个集合的长度不够len,c为剩下的元素数
			//将剩下的数，和倒数一个有序集合归并(倒数一个有序集合的长度为len*2)
			merge(a,size-c-(len<<1),size-c,size-1);
		}

      if(mid==1){//当前有序表的对数为1时结束，上方已经一对完整的有序表排序，并将不足对数的有序表进行了排序
			return;
		}

		mergeSort(a,len*2);
	}
	public static void main(String args[]){
	    int[] a=new int[]{4,3,6,1,2,5,2,2,2,2,0,0,3,1,9,9,9};
		mergeSort(a,1);
		print(a);
	}
	public static void print(int a[]){
		for(int i=0;i<a.length;i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
}

H:\learn\algorithm>javac merge.java

H:\learn\algorithm>java merge
0  0  1  1  2  2  2  2  2  3  3  4  5  6  9  9  9

H:\learn\algorithm>