fac2_9.java

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

//本程序取自王晓东编著“算法分析与设计”第 39 页，例
//线性时间选择问题的解法
import java.lang.System;
  class Random
 {
   private long seed;//当前种子
   private final static long multiplier=0x5DEECE66DL;
   private final static long adder=0xBL;
   private final static long mask=(1L<<48)-1;
   //构造方法，自动产生种子
   public Random(){
     this.seed=System.currentTimeMillis();}
  //构造方法，缺省值0表示由系统自动产生种子
   public Random(long seed)
     {
       if(seed==0)this.seed=System.currentTimeMillis();
       else this.seed=seed;
     }
  //产生[0,n-1]之间的随机整数
   public int random(int n)
     {
      if(n<=0)
       throw new  IllegalArgumentException(" n must be positive");
      seed=(seed*multiplier+adder) & mask;
      return ((int)(seed>>>17)%n);
     }
  //产生[0,1]之间的随机实数
   public double fRandom()
     {
      return random(Integer.MAX_VALUE)/(double)(Integer.MAX_VALUE);
     } 
  }
 //*****************************************************************
   public class Fac2_9{
       private static int partition(int[] a,int p, int r)
     {
      int i = p,
          j = r +1;
      int x = a[p];
      // 将>= 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;
      }
    private static int randomizedPartition(int[] a,int p,int r)
     {
      Random bb=new Random();
      int i1=bb.random(r-p);
     // System.out.println("p="+p+" r="+r+"随机数 "+i1);
      i1=i1+p; 
      swap(a, i1, p);
    // for(int i2=0;i2<a.length;i2++)
    // System.out.print("  "+a[i2]);
    // System.out.println(" ");
     
      return partition (a,p,r);
     }
      
    private static int randomizedSelect(int[] a,int p,int r,int k)
   {
      if (p==r) return a[p];
      int i=randomizedPartition(a,p,r),
          j=i-p+1;
      if (k<=j) return randomizedSelect(a,p,i,k);
      else return randomizedSelect(a,i+1,r,k-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 main(String args[])
  {
     int[]  xx={8,4,3,7,1,5,6,2,10,9,12,11};
      int k=4;
      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(randomizedSelect(xx,0,xx.length-1,k));
  }
}