mergesort.java

《算法设计与分析》王晓东编著

/* 递归描述的合并排序算法  */
public class MergeSort {
	
	public static void mergeSort(Comparable a[],int left,int right)
	{
		Comparable[] b=new Comparable[a.length];
		if (left<right) { // 至少有2个元素
			int i=(left+right)/2;   // 取中点
			mergeSort(a,left,i);
			mergeSort(a,i+1,right);
			merge(a,b,left,i,right);  // 合并到数组b
			copy(a,b,left,right);     // 复制回数组a
		}
	}
  
	public static void merge(Comparable[] c,Comparable[] d,
			                 int L,int m,int r)
	{// 合并c[L:m]和c[m+1,r]到d[L:r]
		int i=L,j=m+1,k=L;
		while (i<=m && j<=r)
			if (c[i].compareTo(c[j])<=0)
				d[k++]=c[i++];
			else
				d[k++]=c[j++];
		if (i>m)
			for (int q=j;q<=r;q++)
				d[k++]=c[q];
		else
			for (int q=i;q<=m;q++)
				d[k++]=c[q];				
	}
	
	public static void copy(Comparable[] dest, Comparable[] sour,
			                int st,int ed)
	{// 把sour[st:ed]内的元素复制到dest[st:ed]中去
		for (int i=st;i<=ed;i++)
			dest[i]=sour[i];	
	}
	
	public static void main(String args[])
	{
		/* 定义一个整数数组：7,21,43,5,123,-2,0,-98,9999 */
		Integer array[]=new Integer[]{
				 new Integer(7),  new Integer(21),  new Integer(43),
				 new Integer(5),  new Integer(123), new Integer(-2),
				 new Integer(0),  new Integer(-98), new Integer(9999)};
		
		/* 对上面的定义的整数数组array进行合并排序 */
		mergeSort(array,0,array.length-1);
		
		/* 显示排序结果 */
		for (int i=0;i<array.length;i++)
		{
			System.out.print(array[i]);
			System.out.print(" ");
		}	
	}    
}
/*  运行结果：
    -98 -2 0 5 7 21 43 123 9999 
 * */