题目：在一个很大的无重复的无序数组中用最快的速度找到第K小的数（或者找到最小的前K个数）。（类似于，在一个有1000000个数的数组中找到最小的100个数）
对于这个问题首先想到的可能是把这个数组进行按从小到大排序，排序完以后就可以直接确定第K小的数字了。但是，这样够快吗？
假设我们是先对数组进行排序，那么肯定会选择最快的排序算法，对于庞大的数组首选当然是快速排序，而且是随机快速排序。现在考虑整个快速排序的过程，分治，递归。这里就不在详细叙述快排的整个过程了，我们的重点在分治的过程，即，首先选定一个主元素key（随机的），经过一趟比较之后，key的左边都是小于key的，key的右边都是大于key的，并且key的位置在之后的排序过程中不会再变化了。整个排序过程我简单理解成一个归为的过程。说到这里应该知道了，一趟遍历完成以后假设key的位置是K，那么我们就可以确定key就是第K小的元素了。快速排序的过程也就可以到此结束了，直接返回K就可以了，原来的数组相当于只排序排一部分，前K个数就是最小的K个数了。
下面是代码的实现：
import java.util.Random;
public class KOfArray {
private static Random rand = new Random();
public static void main(String[] args) {
//无序数组，待查找
int[] arr = {30, 60, 80, 40, 300, 250, 110, 255, 257, 256, 280, 45, 200, 50};
//有序数组，用于对照
int[] arr1 = {30, 40, 45, 50, 60, 80, 110, 200, 250, 255, 256, 257, 280, 300};
//测试对整个数组的的查找结果
for(int i = 1; i < arr.length + 1; ++i){
int r = RandomizedSelect(arr, 0, arr.length - 1, i);
System.out.print(r+" ");
}
}
/**
* 主元素随机选取的划分
* @param arr:待处理数组
* @param p:数组的左边界
* @param r:数组的右边界
* @return:此次选取的主元素一趟排序后的最终下标
*/
private static int RandomizedPartition(int[] arr, int p, int r){
//产生的随机数范围是[p, r-1];
int pivot = rand.nextInt(r-p+1) + p;
//随机产生的元素设为主元素
int x = arr[pivot];
int i = p, j = r;
while(true){
while(arr[i] < x)
i++;
while(arr[j] > x)
j--;
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}else
return j;
}
}
/**
* 非随机划分
* @param arr:待处理数组
* @param p:数组的左边界
* @param r:数组的右边界
* @return:此次选取的主元素一趟排序后的最终下标
*/
private static int Partition(int[] arr, int p, int r){
//将最左边的元素设置为主元素
int pivot = p;
//将主元素调换到数组的最后，方便后续的比较
int temp = arr[r];
arr[r] = arr[pivot];
arr[pivot] = temp;
int x= arr[pivot];
int i = p-1, j = p;
while(j < r){
if(arr[j] <= x){
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
j++;
}
//此时[p, i]范围内的元素都小于主元素，
//[i+1, r-1]内的元素都大于主元素，[r]的元素为主元素，
//只需要将arr[i+1]和主元素的值进行交换就得到一次划分结果,并返回此时主元素位置i+1
temp = arr[i+1];
arr[i+1] =arr[r];
arr[r] = temp;
return i + 1;
}
public static int RandomizedSelect(int[] arr, int p, int r, int i){
if(p == r)
return arr[p];
int q = RandomizedPartition(arr, p, r);//随机选取主元素进行划分
// int q = Partition(arr, p , r);//固定每次选择最左边的元素作为主元素进行划分
if((q+1) == i)
return arr[q];
else if((q+1) < i)
return RandomizedSelect(arr, q+1, r, i);
else
return RandomizedSelect(arr, p, q-1, i);
}
}