mergesort.java

用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装载问题.作业最优处理问韪.

/*
 * MergeSort.java
 *
 * Created on 2006年4月17日, 下午5:04
 *
 * To change this template, choose Tools | Options and locate the template under
 * the Source Creation and Management node. Right-click the template and choose
 * Open. You can then make changes to the template in the Source Editor.
 */

package test;

/**
 *
 * @author michael
 */
public class MergeSort {
    
    /** Creates a new instance of MergeSort */
    public MergeSort() {
    }

      public static void merge(Element[] c,Element[] d,int l,int m,int r){
           int i = l;
           int j = m + 1;
           int 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 <= m;q++)
                    d[k++] = c[q];
           else
                for(int q = i;q <=m;q++)
                     d[k++] = c[q];
      }//merge
    public static void mergePass(Element[] x,Element[] 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];
           }
   }
    //内隐类实现对一个comparable类的归并排序，
    //具体过程Sort通过调用mergePass,mergePass调用merge,不断地对2、4、8....元素进行归并，来实现排序
   public static void sort(Element[] a){
       QSoft(a, 0, a.length-1);
       for (int i=0;i<a.length;i++) System.out.println(a[i].d);
       System.out.println("Sorted");
  }
 static void  QSoft(Element[] e,int Low,int High)
{
	int PriovLoc;
	if (Low<High)
	{
		PriovLoc=Partition(e,Low,High);
		QSoft(e,PriovLoc+1,High);
		QSoft(e,Low,PriovLoc-1);
	}
}
static int Partition(Element[] e,int nLow, int nHigh)
{
	Element Privokey=e[nLow];
		while (nLow<nHigh)
	{
		while (nLow<nHigh && e[nHigh].d>=Privokey.d) nHigh--;
		e[nLow]=e[nHigh];
		while (nLow<nHigh && e[nLow].d<=Privokey.d) nLow++;
		e[nHigh]=e[nLow];
	}
	e[nLow]=Privokey;
	return nLow;
}
      
}