利用快速排序的思想寻找乱序数组第k大数

首先选择轴值，利用快速排序思路将轴值放到合适位置，如果轴值位置恰好在第k位置上，那么轴值便是需要找的值，否则，如果轴值位置大于k，说明要找的数在左半部分；反之则在右半部分。

import java.util.Collections;
import java.util.Vector;

public class FindKth {
 private static int findKth(int[] A, int start, int end, int k) {
  int count = end - start + 1;
  if (count < k)
   return -1;
  int pivot = A[start];
  int i = start, j = end;
  while (i < j) {
   while (j > i && A[j] <= pivot)
    j--;
   A[i] = A[j];
   while (i < j && A[i] > pivot)
    i++;
   A[j] = A[i];
  }
  A[i] = pivot;
  if (i - start + 1 == k)
   return A[i];
  if (i - start + 1 > k)
   return findKth(A, start, i - 1, k);
  else
   return findKth(A, i + 1, end, k - (i - start + 1));
 }
 
 public static void tester() {
  int[] A = new int[1000];
  Vector<Integer> vA = new Vector<Integer>();
  for (int i = 0; i < 1000; ++i)
   vA.add(i);
  Collections.shuffle(vA);
  for (int i = 0; i < 1000; ++i)
   A[i] = vA.get(i);
  System.out.println(findKth(A, 0, A.length - 1, 10));
 }
}