2019独角兽企业重金招聘Python工程师标准>>> 
随机选择实现：
可能经常会提到在数组中找第几小或第几大的问题，这里主要以随机选择(找第i小)来实现，其主要思想还是借助快速排序(http://my.oschina.net/indestiny/blog/203927)当中的划分思想来解决，只不过不用对划分后的两个子数组都做处理，只需处理其中一个，思想比较简洁，实现代码如下：
/**
* 找出数组种从下标p到r之间第i小的数
* @param arr 目标数组
* @param p 数组起始索引
* @param r 数组结束索引
* @param i 第i小?
* @return 第i小的数值
*/
private static int randomSelect(int[] arr, int p, int r, int i) {
if (p == r) return arr[p];
int q = randomPartition(arr, p, r);
int k = q - p + 1;
if (i == k){
return arr[q];
} else if(i < k){ //第i大在左边数组
return randomSelect(arr, p, q-1, i);
} else{ //第i大在右边数组
return randomSelect(arr, q+1, r, i-k);
}
}
/**
* 对数组进行随机划分
* @param arr 待划分数组
* @param p 数组起始索引
* @param r 数组结束索引
* @return 最终基准所在的索引值
*/
private static int randomPartition(int[] arr, int p, int r) {
//[p..r]间产生一个随机索引
int index = Math.random(p, r);
ArrayUtil.swap(arr, index, r);
return partition(arr, p, r);
}
/**
* 对数组进行划分
* @param arr 待划分数组
* @param p 数组起始索引
* @param r 数值结束索引
* @return 基准数的索引
*/
private static int partition(int[] arr, int p, int r) {
int pivot = arr[r];
int i = p-1;
for (int j=p; j<=r-1; j++){
if (arr[j] < pivot){
i++;
ArrayUtil.swap(arr, i, j);
}
}
ArrayUtil.swap(arr, i+1, r);
return i+1;
}int[] arr = new int[]{12, 32,11, 5,13,4};
int target = 2;
int res = randomSelect(arr, 0, arr.length-1, target);
System.out.println("第"+target +"小的是: " + res);