fac2_9_1.java

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

//本程序取自王晓东编著“算法分析与设计”第 41 页，例
//线性时间选择问题的选中位数非随机解法
public class Fac2_9_1{ 
  private static int select (int[] a,int p, int r, int k)
   {
      if (r-p<5) {        //用某个简单排序算法对数组a[p:r]排序;
        bubbleSort(a,p,r);
        return a[p+k-1];
        }
      //将a[p+5*i]至a[p+5*i+4]的第3小元素
      //与a[p+i]交换位置;
      //找中位数的中位数，r-p-4即上面所说的n-5，满5个元素的组数
      for ( int i=0; i<=(r-p-4)/5;i++)
      {
         int s=p+5*i,
             t=s+4;
         for(int j=0;j<3;j++) bubble(a,s,t-j);//只需要下沉3个较大数就足以
         swap(a, p+i, s+2);
      }
            // System.out.println("分组中位数原始数据 ");
            //for(int i1=0;i1<a.length;i1++)
            //  System.out.print("  "+a[i1]);
            //  System.out.println(" ");  
      int x=select(a,p,p+(r-p-4)/5,(r-p+6)/10);
      int i=partition(a,p,r,x),
          j=i-p+1;
            //System.out.println("按中位数划分的位置i="+i+"中位数值x="+x);
            //System.out.println("按中位数划分后数据 ");
            // for(int i2=0;i2<a.length;i2++)
            //System.out.print("  "+a[i2]);
            // System.out.println(" ");      
      if(k<=j) return select(a,p,i,k);
      else return select(a,i+1,r,k-j);
   }
       private static int partition(int[]a,int p, int r,int p1)
     {
      int i = p,
          j = r +1;
      int x = p1;
      // 将>= x的元素交换到左边区域
      // 将<= x的元素交换到右边区域
      while (true) {
        while(i<a.length && (a[++i]-x)<0);
        while(j!=0 && (a[--j]-x)>0);
        if (i >=j) break;
      swap(a, i, j);
        }
      a[p]= a[j];
      a[j]= x;
      return j;
      }
     public static void bubbleSort(int[] a,int p,int r)
      {
        for(int i=p;i<r;i++)
          for(int j=i;j<=r;j++)
           if(a[i]>a[j])swap(a,i,j);
      }
    public static void swap(int[] a1,int m,int n)
      {
         int temp;
         temp=a1[m];
         a1[m]=a1[n];
         a1[n]=temp;

      }
     public static void bubble(int[] a1,int x,int y)
      {
       
         for(int n=x;n<=y;n++)
           if(a1[y]<a1[n])swap(a1,y,n);
       }
  
 public static void main(String args[])
  {
      int[]  xx={8,4,3,7,1,6,5,9,2,12,11,10,13};
      int k=5;
      System.out.println("原始数据 ");
      for(int i=0;i<xx.length;i++)
     System.out.print("  "+xx[i]);
     System.out.println(" ");           
     System.out.println("第 "+k+" 小的数据为 ");
     System.out.println(select(xx,0,xx.length-1,k));
}
}