import java.util.Arrays;

/**
* 选择问题，确定N个数中第K个最大值
* @author wulei
* 将前k个数读进一个数组，冒泡排序（递减），再将剩下的元素逐个读入，
* 如果新元素小于第K个元素，忽略，否则将新元素插入正确的位置，并移除原第K个元素。
*/
public class SelectTest {

//public static final Random RANDOM = new Random(3);
//3为随机数种子，当种子相同的时候，每次随机生成的数都一样。
//RANDOM.nextInt(100) 生成0到100的整数。

//冒泡
public static void sort(int[] arr){
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-i-1; j++) {
if(arr[j] < arr[j+1]){
int x = arr[j];//TODO 测试new基本类型的性能，待会儿放到全局
arr[j] = arr[j+1];
arr[j+1] = x;
}
}
}
}

public static int selectK(int[] arr,int k){
int[] kArr = Arrays.copyOf(arr, k);
sort(kArr);
for (int i = k; i < arr.length; i++) {
if(arr[i] > kArr[k-1]){
kArr[k-1] = kArr[k-2];
for (int j = k-2; j >= 0; j--) {
if(kArr[j] > arr[i]){
kArr[j+1] = arr[i];//复杂问题简单化:如果新元素比a[j]小，那么在a[j]后面,大，那么占用a[j]
break; //的位置，但需要先将a[j]往后移。
}else{
kArr[j+1] = kArr[j];
kArr[j] = arr[i];
}
}
}
}
return kArr[k-1];
}

public static void main(String[] args){
int[] arr = new int[]{3,2,1,9,0,0,0,0,0,10,11,8};
long start = System.currentTimeMillis();
int ka = selectK(arr, 3);
System.out.println("time:"+(System.currentTimeMillis()-start));
System.out.println(Arrays.toString(arr));
System.out.println(ka);
}

}