//本程序取自Clifford A.Shaffer著張銘等譯“數據結構與算法分析”第 163 頁，例8.4
//快速排序問題解法
//Quick sort
import java.io.*;
class Examp8_4
 {
  static void qsort(int[] array,int i,int j)
     {
      int pivotindex=findpivot(array ,i,j); //pick a pivot
       swap(array,pivotindex,j);
      // Stick pivot at end k will be the forst position in the right subarray
      int k=partition(array,i-1,j,key(array,j));
       swap(array,k,j);               //put pivot in place
       if((k-i)>1)qsort(array,i,k-1); //sort left partition
       if((j-k)>1)qsort(array,k+1,j); //sort right partition 
     } 
  static int findpivot(int[] a,int i,int j)
     {
      return(i+j)/2;
     }
   static int partition(int[] array,int l,int r,int pivot)
     {  
     do{        //move the bounds inward until they meet
       while(key(array,++l)<pivot); // move left bound right
       while((r!=0) && (key(array,--r)>pivot));//move right bound
       swap(array,l,r) ; //swap out-of-plac values
       }while(l<r);  //stop when they cross
       swap(array,l,r); //reverse last ,wasted swap
     return l;  // return first position in right partition
     }
   public static void swap(int[] q,int i,int j)
     {
      int temp;
      temp=q[i];q[i]=q[j];q[j]=temp;
     }
  public static int key( int [] q,int p)
     {  return q[p];}
  public static void main(String args[]) 
     {
     int[] a={59,20,17,13,28,14,23,83,36,98,11,70,65,41,42,15};
     System.out.println("quick排序之前");
     for(int i=0;i<=a.length-1;i++)
     System.out.print(a[i]+"  ");
     System.out.println();
   qsort(a,0,a.length-1);
     System.out.println("quick排序之后");
     for(int i=0;i<=a.length-1;i++)
     System.out.print(a[i]+"  ");
     System.out.println();
    }
 }