开始
public class FindKth {
public int findKth(int[] arr, int left, int right, int k) {
int i;
if (left > right) {
return -1;
} else {
i=partion(arr, left, right);
if (i-left+1 == k) {
return arr[i];
} else if (i-left+1 > k) {
return findKth(arr, left, i - 1, k);
} else {
return findKth(arr, i + 1, right, k-i-1);
}
}
}
public int partion(int[] arr, int left, int right) {
int t;
int i = left, j = right;
int tmp = arr[left];
while (i != j) {
while (arr[j] >= tmp && i < j) {
j--;
}
while (arr[i] <= tmp && i < j) {
i++;
}
if (i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left]=arr[i];
arr[i]=tmp;
return i;
}
public static void main(String[] args) {
int[] arr = { 2, 1, 55, 62, 13, 41, 22, 8, 77, 82, 16, 33 };
System.out.println(new FindKth().findKth(arr, 0, arr.length - 1, 3));
}
}
结束
