九乡新闻网:算法设计与分析 2.9 线性时间选择
来源：百度文库 编辑：九乡新闻网 时间：2024/04/29 09:39:11
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));
}
}