//本程序取自王曉東編著“算法分析與設(shè)計”第 41 頁，例
//線性時間選擇問題的選中位數(shù)非隨機解法
public class Fac2_9_1{ 
  private static int select (int[] a,int p, int r, int k)
   {
      if (r-p<5) {        //用某個簡單排序算法對數(shù)組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]交換位置;
      //找中位數(shù)的中位數(shù)，r-p-4即上面所說的n-5，滿5個元素的組數(shù)
      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個較大數(shù)就足以
         swap(a, p+i, s+2);
      }
            // System.out.println("分組中位數(shù)原始數(shù)據(jù) ");
            //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("按中位數(shù)劃分的位置i="+i+"中位數(shù)值x="+x);
            //System.out.println("按中位數(shù)劃分后數(shù)據(jù) ");
            // 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的元素交換到左邊區(qū)域
      // 將<= x的元素交換到右邊區(qū)域
      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("原始數(shù)據(jù) ");
      for(int i=0;i<xx.length;i++)
     System.out.print("  "+xx[i]);
     System.out.println(" ");           
     System.out.println("第 "+k+" 小的數(shù)據(jù)為 ");
     System.out.println(select(xx,0,xx.length-1,k));
}
}