1 import  java.util.Random ;  2  3 /** 4  *快速排序思路：用到了分治法 5  *    一个数组A[0,n-1] 分解为三个部分，A[0,p - 1] , A[p] , A[p + 1, n-1] 6  *    递归调用快速排序，对A[0,p - 1]和A[p + 1,n-1]进行排序 7  * 8  */ 9 public  class  QuickSort10 {11     /**12      *快速排序主方法13      *14      */15     public  static  void  quickSort(int[] resouceArr , int  begin , int  end)16     {17         if( begin  <  end )18         {19             int  part = _partition(resouceArr , begin , end );20             quickSort(resouceArr , begin , part - 1 );21             quickSort(resouceArr , part + 1  , end );22 23         }24     }25 26     /**27      *随机化快速排序主方法28      *29      */30     public  static  void  randomizedQuickSort(int[] resouceArr , int  begin , int  end)31     {32         if( begin  <  end )33         {34             int  part = _randomizedPartition(resouceArr , begin , end );35             quickSort(resouceArr , begin , part - 1 );36             quickSort(resouceArr , part + 1  , end );37 38         }39     }40 41     /**42      *随机算法快速排序：把A[p]随机化，不限于数组尾部,把数组A[p]与数组尾部的数调换43      *44      */45     private  static  int   _randomizedPartition(int[] arr , int begin , int end )46     {47         //随机函数产生随机数48         Random  r = new Random();49         int  i =  r.nextInt(end + 1) + begin ;50         int  temp = arr[end] ;51         arr[end] = arr[i] ; 52         arr[i] = temp ;53         54         return  _partition(arr , begin  ,  end  );        55     }56 57     /**58      *partition对部分数组进行原址重排59      *60      */61     private  static   int  _partition(int[] arr , int  begin , int end)62     {63         //选取一个元素作为分界元素，这里选取的是最后一个元素64         int  part = arr[end] ; 65         //i从-1开始，j从1开始66         int  i  =  begin -1 ; 67         for(int j = begin ; j <=  end - 1 ; j++)68         {69             if(arr[j] <= part)70             {71                 i = i + 1 ;72                 int  temp = arr[i];73                 arr[i] = arr[j];74                 arr[j] = temp ; 75             }76         }77         int  temp1 = arr[i+1];78         arr[i+1] = arr[end];79         arr[end] = temp1 ; 80         return  i + 1 ;81     }82     83 }