fac2_8_1.java

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

//本程序取自王晓东编著“算法分析与设计”第 37 页，例
//快速排序问题的解法
  public class Fac2_8_1{

   static int findpivot(int[] a,int i,int j)
      { return(i+j)/2;}
  
    private static int partition(int[] a,int p, int r,int pivot)
     {
      do{     
        while((p<a.length-1) && (a[++p]-pivot)<0);              // 将>= x的元素交换到左边区域
        while((r!=0) && (a[--r]-pivot)>0);                     // 将<= x的元素交换到右边区域
        swap(a, p, r);
        }while(p<r);
      swap(a, p, r);
      return p;
      }
     public static void QuickSort(int[] a,int p,int r)
       {
        int pi=findpivot(a,p,r);
        swap(a,pi,r);
        int q=partition(a,p-1,r,a[r]);
        swap(a,q,r);
        if((q-p)>1) QuickSort(a,p,q-1);        
        if((r-q)>1) QuickSort(a,q+1,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 main(String args[])
     {
      int[]  xx={1,4,3,7,8,5,6,2};
      System.out.println("下面为原输入数据 ");
      for(int i=0;i<xx.length;i++)
      System.out.print("  "+xx[i]);
      System.out.println(" ");        
      QuickSort(xx,0,xx.length-1);
      System.out.println(" 下面为排序后数据");
     for(int i=0;i<xx.length;i++)
     System.out.print("  "+xx[i]);
     System.out.println(" ");
     }
 }