随机选择实现：

可能经常会提到在数组中找第几小或第几大的问题，这里主要以随机选择(找第i小)来实现，其主要思想还是借助快速排序()当中的划分思想来解决，只不过不用对划分后的两个子数组都做处理，只需处理其中一个，思想比较简洁，实现代码如下：

/** * 找出数组种从下标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);