//本程序取自王曉東編著“算法分析與設計”第 37 頁，例
//快速排序問題的解法
 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);
     } 
  }
 class Quick{
     static int[] a; 
    public Quick(int[] y)
    { a=y;} 
    private static int partition(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);
      System.out.println("i= "+i);   
        while(j!=0 && (a[--j]-x)>0);
      System.out.println("    j= "+j);
        if (i >=j) break;
      swap(a, i, j);
        }
      a[p]= a[j];
      a[j]= x;
      return j;
      }
    private static int randomizedPartition(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 (p, r);
     }
      
    public static void swap(int[] x,int m,int n)
      {
         int temp;
         temp=x[m];
         x[m]=x[n];
         x[n]=temp;
      }
     public static void randomizedQuickSort(int p,int r)
       {
        if(p<r){
          int q=randomizedPartition(p,r);
          randomizedQuickSort(p,q-1);
          randomizedQuickSort(q+1,r);
          }
       }
   }
   public class Fac2_8{
     public static void main(String args[])
     {
      int[]  xx={8,4,3,7,1,5,6,2};
      System.out.println("原始數據 ");
      for(int i=0;i<xx.length;i++)
     System.out.print("  "+xx[i]);
     System.out.println(" ");
      Quick x=new Quick(xx);           
     x.randomizedQuickSort(0,xx.length-1);
     System.out.println("排序后數據 ");
     for(int i=0;i<x.a.length;i++)
     System.out.print("  "+x.a[i]);
     System.out.println(" ");
     }
 }