import java.util.Random ; /** *快速排序思路:用到了分治法 * 一个数组A[0,n-1] 分解为三个部分,A[0,p - 1] , A[p] , A[p + 1, n-1] * 递归调用快速排序,对A[0,p - 1]和A[p + 1,n-1]进行排序 * */ public class QuickSort { /** *快速排序主方法 * */ public static void quickSort(int[] resouceArr , int begin , int end) { if( begin < end ) { int part = _partition(resouceArr , begin , end ); quickSort(resouceArr , begin , part - 1 ); quickSort(resouceArr , part + 1 , end ); } } /** *随机化快速排序主方法 * */ public static void randomizedQuickSort(int[] resouceArr , int begin , int end) { if( begin < end ) { int part = _randomizedPartition(resouceArr , begin , end ); quickSort(resouceArr , begin , part - 1 ); quickSort(resouceArr , part + 1 , end ); } } /** *随机算法快速排序:把A[p]随机化,不限于数组尾部,把数组A[p]与数组尾部的数调换 * */ private static int _randomizedPartition(int[] arr , int begin , int end ) { //随机函数产生随机数 Random r = new Random(); int i = r.nextInt(end + 1) + begin ; int temp = arr[end] ; arr[end] = arr[i] ; arr[i] = temp ; return _partition(arr , begin , end ); } /** *partition对部分数组进行原址重排 * */ private static int _partition(int[] arr , int begin , int end) { //选取一个元素作为分界元素,这里选取的是最后一个元素 int part = arr[end] ; //i从-1开始,j从1开始 int i = begin -1 ; for(int j = begin ; j <= end - 1 ; j++) { if(arr[j] <= part) { i = i + 1 ; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp ; } } int temp1 = arr[i+1]; arr[i+1] = arr[end]; arr[end] = temp1 ; return i + 1 ; } }