//本程序取自王曉東編著“算法分析與設計”第 170 頁，例
//Element類合并排序的遞歸解法（單位價值升序排序）
class mergeSort2_7_2
  {
     private  static class Element implements Comparable
        {
          int id;//物品編號
          double d;
          private Element(int idd,double dd)
           {
             id=idd;
             d=dd;
           }
        public int compareTo(Object x)
           {
             double xd=((Element) x).d;
             if(d<xd)return -1; 
             if(d==xd)return 0;
             return 1;
           }
       public boolean equals(Object x)
          {return d==((Element) x).d;}
      }
     
   public static void mergeSort(Element [] a,int left,int right)
    {
     Element b[]=new Element[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 copy(Element[] a,Element[] b,int i,int j)
    {
      int k;
      for(k=i;k<=j;k++)
      a[k]=b[k];
     } 
  public static void merge(Element [] c,Element [] 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].d-c[j].d<=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[])
     {
     double  c;                          // 背包容量
     int n;                              // 物品數 
     double []ww={0,3d,5d,2d,1d} ;       // 物品數量數組 
     double []pp={0,9d,10d,7d,4d};       // 物品價值數組
        n=4;                    //注意上述原始數據增加0，以保持程序通用性
        c=7; 
      Element []q=new Element[n];
     //初始化   q[0,n-1]

     for(int i=1;i<=n;i++)
      q[i-1]= new Element(i,pp[i]/ww[i]);
      for(int i=0;i<q.length;i++)
      System.out.print(q[i].d+"  ");
      System.out.println();
      mergeSort(q,0,q.length-1);
       for(int i=0;i<q.length;i++)
      System.out.print(q[i].d+"  ");
      System.out.println();
     }
  }