public class SelectK {

public static  <E extends Comparable<E>> Object selectK(E[] arr,int k){
        Random random = new Random();
return selectK(arr,arr.length-k,0,arr.length-1,random);
    }

private static <E extends Comparable<E>> Object selectK(E[] arr, int k, int l, int r, Random random){
if (l>r) return -1;
int p = partition(arr,l,r,random);
if (arr[p].compareTo(arr[k])==0)return arr[p];
if (arr[p].compareTo(arr[k])<0)
return selectK(arr,k,p+1,r,random);
return selectK(arr,k,l,p-1,random);
    }

private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random random) {
int p = l+random.nextInt(r-l+1);
swap(arr,l,p);
int i = l + 1 , j = r ;
while (true){
while (i <= j&&arr[i].compareTo(arr[l]) < 0)
                i++;

while (j >=i &&arr[j].compareTo(arr[l]) > 0)
                j--;

if (i>=j)break;

swap(arr,i,j);
            i++;
            j--;
        }
swap(arr,l,j);

return j;
    }

private static <E extends Comparable<E>> void swap(E[] arr, int l, int p) {
E temp = arr[l];
        arr[l] = arr[p];
        arr[p] = temp;
    }

public static void main(String[] args) {
        Integer[] arr = new Integer[]{3,3,3,3,4,3,3,3,3};
for (int i = 0; i < 100; i++) {
            System.out.print(selectK(arr,1)+" ");

        }
    }

}

老师你好，跑这个Main有时候会出现4 有时候会出现3 检查了好几遍了还没找到错误