题目：以尽量高的效率求出一个乱序数组中按数值顺序的第k 的元素值
思路：这里很容易想到直接排序然后顺序查找，可以使用效率较高的快排，但是它的时间复杂度是O(nlgn)，我们这里可以用一种简便的方法，不一定需要排序，使用快速排序中双向分区的扫描方法，这里使用的是优化过后的三点中值法，具体思想一样，只是主元的取法不一样。然后扫描出主元下标，然后根据主元的值将数组划分成一半大，一半小。然后再根据主元下标与k进行比较，如果相等，说明主元就是我们要找的数，如果大于k，说明k所代表的值在小的那边，继续向小的那部分递归，如果小于k，说明k代表的值在大的那边，继续向大的那部分递归。这样即可得出正确答案。这种方法的时间复杂度为O(n)，因为每次递归都相当于舍弃掉了差不多一半的数。
代码：
import java.util.Arrays;
public class SelectK {
public static void main(String[] args) {
int arr[] = new int[10];
for(int i=0;i<10;i++){
arr[i] = (int) ((Math.random()+1)*10);
}
System.out.println("查找前数组："+Arrays.toString(arr));
int k = selectK(arr, 0, arr.length-1, 5);
System.out.println("查找出第k小的元素："+k);
}
/**
*
* @param arr
* @param p 开始下标
* @param r 结束下标
* @param k 求第k小元素 （递增第k个元素）
* @return
*/
public static int selectK(int[] arr,int p,int r,int k){
int q = partition(arr, p, r); // 主元的下标
int qk = q - p + 1; // 主元是第几个元素
if (qk==k) {
return arr[q];
}else if (qk>k) {
return selectK(arr, p, q-1, k);
}else {
return selectK(arr, q+1, r, k-qk);
}
}
//三点中值法
public static int partition(int[] arr, int p, int r) {
//优化，在p, r, mid之间，选一个中间值作为主元
int midIndex = p + ((r - p) >> 1);//中间下标
int midValueIndex = -1;//中值的下标
if(arr[p] <= arr[midIndex] && arr[p] >= arr[r]) {
midValueIndex = p;
}else if(arr[r] <= arr[midIndex] && arr[r] >= arr[p]) {
midValueIndex = r;
}else {
midValueIndex = midIndex;
}
swap(arr, p, midValueIndex);
int pivot = arr[p];
int left = p + 1; //左侧指针
int right = r; //右侧指针
while(left <= right) {
while(left <= right && arr[left] <= pivot) {
left++;
}
while(left <= right && arr[right] > pivot) {
right--;
}
if(left < right) {
swap(arr, left, right);
}
}
swap(arr, p, right);
return right;
}
private static void swap(int[] A, int p, int bigger) {
int temp = A[p];
A[p] = A[bigger];
A[bigger] = temp;
}
}
结果：
