/**
* 问题：从一个由n个不同的数组构成的集合中选择其第i个顺序统计量的问题
* 解决：采用类似快速排序的思想即对输入数组进行递归划分，不同之处是，快速排序会递归处理划分的两边，
* 而此方法只处理划分的一边。
* 最坏时间复杂度为：O(n^2),平均运行的时间复杂度为O(n)
*/
public class RandomizedSort {
/**
* 对arr进行递归划分，每次划分判断主元元素是否为要找的顺序统计量，如果不是，判断要找的顺序统计量在那一个子数组，然后再进行划分
* @param arr 数组
* @param p 开始下标
* @param r 结束下标
* @param i 第i个顺序统计量
*/
public int randomizedSort(int arr[],int p,int r,int i){
if(p==r)
return arr[p];
//对arr数组进行划分，arr[q]即为数组arr的第q-p+1个顺序统计量
int q = partition(arr,p,r);
int k = q-p+1;
//如果i等于k，那么arr[q]即为第i个顺序统计量(第i小的元素)
if(i==k)
return arr[q];
//如果i小于k，说明第i个顺序统计量在arr[p..q-1]中
else if(i<k)
return randomizedSort(arr,p,q-1,i);
//如果i大于k，说明第i个顺序统计量在arr[q+1..r]中，只是在新数组中，第i个顺序统计量就成了第i-k个顺序统计量
else
return randomizedSort(arr,q+1,r,i-k);
}
/**
* 对数组arr[p..r]划分成a[p..q]和a[q+1..r]两个子数组，其中a[p..q]中的元素都小于a[q]，
* a[q+1..r]中的元素都大于a[q]。
* @param arr 需要划分的数组
* @param p 数组起始下标
* @param r 数组结束下标
*/
public int partition(int arr[],int p,int r){
//采用随机算法，期望在平均情况在，对数组的划分能比较均称
int x = (int) (Math.random()*(r-p)+p);
//arr[x]与arr[r]交换
int temp = arr[x];
arr[x] = arr[r];
arr[r] = temp;
//i为小元素部分中下标最大的位置，也就是它的下一个位置(即i+1)就是大元素部分下标最小的位置，初始化为p的前一个位置
int i = p-1;
//从p个元素开始，一直检查到r前面的一个元素
for(int j=p;j<r;j++){
//如果arr[j]是比arr[r]小的元素，要放在小元素位置，由于i标记的是小元素部分下标最大的位置，
//所以arr[j]应该被换到i+1的位置
if(arr[j]<temp){
i++;
int w = arr[j];
arr[j]= arr[i];
arr[i]= w;
}
}
//最后把arr[r]放在小元素部分和大元素部分中间
arr[r] = arr[i+1];
arr[i+1] = temp;
return i+1;
}
//测试.....
public static void main(String[] args) {
int arr[] = {3,2,9,0,7,5,4,8,6,1};
RandomizedSort rs = new RandomizedSort();
int result = rs.randomizedSort(arr, 0, arr.length-1, 5);
System.out.println(result);
}
}