mergesort2_7.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 34页，例
//合并排序的非递归解法
class mergeSort2_7
  {
   public static void mergeSort(int [] a)
    {
     int [] b=new int[a.length];
     int s=1;
     while(s<a.length){
        mergePass(a,b,s);//合并到数组 b
        s+=s;
        mergePass(b,a,s);//合并到数组 a
        s+=s;
        }
     }
   public static void mergePass(int [] x,int [] y,int s)
     {//合并大小为s的相邻子数组 
      int i=0;
      while(i<=x.length-2*s)
      {//合并大小为s的相邻2段子数组
      merge(x,y,i,i+s-1,i+2*s-1);
      i=i+2*s;
      }
      //剩下的元素个数少于2s
      if(i+s<x.length)
      merge(x,y,i,i+s-1,x.length-1);
      else
      //复制到y
      for(int j=i;j<x.length;j++)
       y[j]=x[j];
     }
  public static void merge(int [] c,int [] d,int l,int m,int r)
     {//合并c[l:m]和c[m+1:r]到d[l:m]
      int i=l,
          j=m+1,
          k=l;
      while((i<=m)&&(j<=r))
          if(c[i]-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 main(String args[])
     {
      int i;
      int t[]={4,8,3,7,1,5,6,2};
      for(i=0;i<t.length;i++)
      System.out.print(t[i]+"  ");
      System.out.println();
      mergeSort(t);
       for(i=0;i<t.length;i++)
      System.out.print(t[i]+"  ");
      System.out.println();
     }
  }