算法设计与分析 2.9 线性时间选择

import java.util.Date;
import java.util.Random;

public class Select {
 
 private static int randomPartition(int[] data, int start, int end) {
  Random rand = new Random(new Date().getTime());
  int index = rand.nextInt(data.length);
  swap(data, 0, index);
  return partition(data, start, end);
 }
 private static int partition(int[] data, int start, int end) {
  int var = data[start];
  int i = start + 1;
  int j = end;
  for (;;) {
   while (data[i] < var)
    i++;
   while (data[j] > var)
    j--;
   if (i >= j)
    break;
   else
    swap(data, i, j);

  }
  data[start] = data[j];
  data[j] = var;
  return j;
 }

 private static void swap(int[] data, int i, int j) {
  int temp = data[i];
  data[i] = data[j];
  data[j] = temp;
 }

 public static int select(int[] data, int start, int end, int k) {
  if (start == end)
   return data[start];

  int mid = randomPartition(data, start, end);
  int size = mid - start + 1;
  if (k <= size)
   return select(data, start, mid, k);
  else
   return select(data, mid + 1, end, k - size);

 }
 
 public static void main(String[] args) {
  int[] data = {2, 1, 4, 5, 3,};
  System.out.println(select(data, 0, data.length - 1, 5));
 }
}