fac2_8_2.java

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

//本程序取自王晓东编著“算法分析与设计”第 37 页，例2.8
//快速排序问题的解法
//由于采用随机数，每次执行情况不同，可能会产生错误，必须多试几次
 import java.lang.System;
 import java.util.Random;
 import java.lang.Math;

 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=Math.abs(bb.nextInt())%(r-p+1)+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_2{
     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(" ");
     }
 }