mergesort.java

01背包四种算法实现(java版)

/*
 * MergeSort.java
 *
 * Created on 2007年6月15日, 下午6:08
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package sunfa;

/**
 *
 * @author Administrator
 */

public class MergeSort {
	public static void mergeSort(Comparable[]a){
		Comparable [] b = new Comparable[a.length];
		int s=1;
		while(s<a.length){
			mergePass(a,b,s);
			s+=s;
			mergePass(b,a,s);
			s+=s;
		}
	}
	
	public static void mergePass(Comparable[] x,Comparable[]y,int s){
		int i=0;
		while(i<=x.length-2*s){
			merge(x,y,i,i+s-1,i+2*s-1);
			i=i+2*s;
		}
		if(i+s<x.length)
			merge(x,y,i,i+s-1,x.length-1);
		else 
			for(int j=i;j<x.length;j++)
				y[j]=x[j];
	}
	
	public static void merge(Comparable[]c,Comparable[]d,int l,int m,int 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];
	}
}